{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 顺序容器（Sequence Containers）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::vector<T>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/vector.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 连续堆内存，指数式扩容；C++11 起全面移动语义，`allocator_traits` 统一分配器接口；C++23 增补 `resize_and_overwrite`、广泛 `constexpr` 支持 |\n",
    "| 优点       | 随机访问 O(1)，尾部插入摊还 O(1)；与 C API、ranges、`std::span` 协同良好 |\n",
    "| 缺陷       | 中间插删 O(n)；扩容会使迭代器失效；`vector<bool>` 位压缩带来性能/语义问题 |\n",
    "| 时间复杂度 | 访问：O(1)；`push_back`：摊还 O(1)；任意插删：O(n)           |\n",
    "| 空间复杂度 | O(n) 连续存储，冗余容量约 [n, 2n)                            |\n",
    "| 常见互转   | 可用区间构造或 `std::ranges::to<vector>` 从 `deque`、`list`、`forward_list`、`array`、`string`、`string_view`、`span` 转换；`std::span`/`std::mdspan` 可零拷贝视图化 |\n",
    "\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本            | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| --------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++11           | `std::vector` 满足 `AllocatorAwareContainer`；全面支持移动构造/赋值与 `emplace`/`emplace_back`；新增 `cbegin`/`cend`/`crbegin`/`crend` 等只读迭代器成员；元素类型约束从 `CopyConstructible`/`CopyAssignable` 放宽为按具体操作满足 `Erasable` | 减少元素拷贝成本，容器在扩容/插入时优先采用移动语义；通过显式 `emplace` 提升构造效率；可与常量迭代器更安全地协作 |\n",
    "| C++14           | 未引入结构性新特性（主要为缺陷修正）                         | 行为与 C++11 一致，依旧使用 C++11 的移动语义与迭代器接口     |\n",
    "| C++17           | 引入 `std::pmr::vector`（多态分配器别名）；`std::vector` 被正式标记为 `ContiguousContainer`；支持以不完整类型实例化（`__cpp_lib_incomplete_container_elements`，值 201505L）；提供类模板实参推导指引（CTAD） | 容器可与 `pmr::memory_resource` 协作实现内存池；标准保障连续存储语义；可在头文件中声明以不完整类型成员的 `vector`；直接使用列表初始化推导元素类型 |\n",
    "| C++20           | 所有成员函数 `constexpr` 化；要求 `Allocator::value_type` 必须与 `T` 相同（否则程序不合格）；新增非成员 `erase`/`erase_if`；提供三路比较（`<=>`） | 允许在常量表达式中调用大多数 `vector` 成员（但容器本身仍因动态分配通常不可 `constexpr`）；强化分配器一致性；便捷批量按谓词删除元素；比较运算与现代排序/排序检测兼容 |\n",
    "| C++23           | 新增 `assign_range`、`insert_range`、`append_range`、`erase(iterator, iterator)` ranges 重载；`resize_and_overwrite`（DR）提升重写能力；支持 `std::ranges::to<std::vector>` 等构造；对应特性测试宏 `__cpp_lib_containers_ranges`=202202L | 与 ranges 框架深度整合，方便从任意 `range` 构造或插入；`resize_and_overwrite` 允许原位写入新元素提升性能；ranges 重载减少中间容器创建 |\n",
    "| Feature-test 宏 | `__cpp_lib_incomplete_container_elements`=201505L（C++17）<br>`__cpp_lib_containers_ranges`=202202L（C++23）<br>`__cpp_lib_ranges_reserve_hint`=202502L（计划进入 C++26） | 通过宏判定编译器对相关能力的支持；后者预示未来 `ranges::reserve_hint` 与 `vector` 的协作能力 |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::deque<T>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/deque.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 分段缓冲区 + 中控器（map）；C++11 起支持移动、`allocator_traits`，C++23 几乎全 `constexpr` |\n",
    "| 优点       | 头尾插删 O(1)；随机访问几乎 O(1)；扩容无需整体搬移           |\n",
    "| 缺陷       | 中间插删 O(n)；缓存局部性较差；难以直接暴露为 `std::span`    |\n",
    "| 时间复杂度 | 头尾插删：O(1)；随机访问：O(1)；中部插删：O(n)               |\n",
    "| 空间复杂度 | O(n) 数据 + O(b) 缓冲指针开销，碎片较多                      |\n",
    "| 常见互转   | 可用迭代器区间构造转换为 `vector`、`list`、`string`；可作为 `std::queue`/`std::stack`/`std::priority_queue` 的底层容器；ranges `to<deque>` 支持从任何可迭代范围获取 |\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++11             | `std::deque` 满足 `AllocatorAwareContainer`；引入 `emplace`/`emplace_front`/`emplace_back` 以及对应的 `push`/`pop` 迭代器安全规则更新；新增 `cbegin`/`cend`/`crbegin`/`crend` 常量迭代器成员；放宽元素类型要求为按操作满足 `Erasable`；修订迭代器失效语义（如对 `pop_front`/`pop_back` 保持非擦除元素引用稳定） | 构造插入可原地构造减少复制；常量迭代器提升 const 场景安全性；更明确的迭代器失效规则便于写出健壮代码 |\n",
    "| C++14             | 主要为缺陷修正与实现细化，无新增核心功能                     | 行为与 C++11 基本一致                                        |\n",
    "| C++17             | 提供 `std::pmr::deque` 多态分配器别名；允许以类模板实参推导指引（CTAD）直接推导元素类型；继续巩固迭代器/引用稳定性规定 | 便于与 `pmr::memory_resource` 协作实现自定义内存池；列表初始化时无需显式写模板实参 |\n",
    "| C++20             | `Allocator::value_type` 必须与 `T` 一致（不符则程序非良构）；新增非成员 `erase`/`erase_if`；引入三路比较运算符 `<=>`（保留传统比较移至 C++20 之前） | 强化分配器契约，避免隐藏错误；`erase_if` 快速按谓词批量删除；三路比较便于与 `<algorithm>` 和排序策略协作 |\n",
    "| C++23             | 引入 ranges 友好接口：`assign_range`、`insert_range`、`append_range`、`prepend_range`；`ranges::to<deque>` 与其他 ranges 构造可用；特性宏 `__cpp_lib_containers_ranges`=202202L | 与 ranges 框架无缝对接，从任意 range 批量构造/插入；减少中间容器开销 |\n",
    "| C++26（提案阶段） | 计划将所有成员函数 `constexpr` 化（特性宏 `__cpp_lib_constexpr_deque`=202502L）；迭代器满足 `ConstexprIterator` 要求 | 编译期容器操作能力显著增强，适合 constexpr 算法和元编程场景（取决于编译器支持） |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::list<T>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/list.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 双向链表节点（前驱/后继指针）；C++11 起 `emplace`、移动语义；C++20 起大量操作 `constexpr` |\n",
    "| 优点       | 任意位置插删 O(1)；迭代器稳定；`splice/merge` 常数时间       |\n",
    "| 缺陷       | 不支持随机访问；节点内存占用大；缓存不友好                   |\n",
    "| 时间复杂度 | 插删：O(1)；定位第 i 个：O(n)；查找：O(n)                    |\n",
    "| 空间复杂度 | O(n) 数据 + 每节点约 2 指针                                  |\n",
    "| 常见互转   | 可用迭代器区间构造转换为 `vector`、`deque`、`forward_list`；`splice`/`merge` 可在 `list` 间零拷贝转移；ranges `to<list>` 支持 |\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++11             | `std::list` 满足 `AllocatorAwareContainer`；新增 `emplace`/`emplace_front`/`emplace_back`；提供 `cbegin`/`cend`/`crbegin`/`crend` 等常量迭代器；元素类型约束放宽为按操作满足 `Erasable` | 支持原地构造减少拷贝，const 迭代器令只读遍历更安全；列表可容纳更多类型（含仅可移动类型） |\n",
    "| C++14             | 主要缺陷修复，无显著新特性                                   | 行为与 C++11 基本一致                                        |\n",
    "| C++17             | 引入 `std::pmr::list` 多态分配器别名；类模板实参推导指引（CTAD）；支持以不完整类型实例化（特性宏 `__cpp_lib_incomplete_container_elements`=201505L） | 容器可与 `pmr::memory_resource` 协作共享内存；可免写模板参数直接构造；能在声明阶段以前向声明类型定义 `list` 成员 |\n",
    "| C++20             | 要求 `Allocator::value_type == T`（否则程序非良构）；非成员 `erase`/`erase_if`；新增三路比较 `<=>`（传统关系运算被移除） | 强化分配器一致性；按谓词删除更便捷；与 `<algorithm>` 新接口兼容 |\n",
    "| C++23             | ranges 支持：`assign_range`、`insert_range`、`append_range`、`prepend_range` 等；特性宏 `__cpp_lib_containers_ranges`=202202L | 与 ranges 框架无缝协作，可从任意 `range` 批量操作；降低中间容器成本 |\n",
    "| C++26（提案阶段） | 计划将成员函数 `constexpr` 化（特性宏 `__cpp_lib_constexpr_list`=202502L），迭代器满足 `ConstexprIterator` | 若实现支持，可在常量表达式上下文操作 `list`，适用于编译期算法 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::forward_list<T>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/forward_list.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 单向链表（承袭 SGI `slist`）；C++11 引入，C++20 后 `constexpr` 化 `splice_after` 等 |\n",
    "| 优点       | 额外开销低；头部插入 O(1)；适合单向流式处理                  |\n",
    "| 缺陷       | 无 `size()`；只能单向遍历；插入需掌握前驱                    |\n",
    "| 时间复杂度 | 头部插入：O(1)；查找/访问：O(n)                              |\n",
    "| 空间复杂度 | O(n) 数据 + 每节点 1 指针                                    |\n",
    "| 常见互转   | 可区间构造转为 `vector`、`deque`、`list`；ranges `to<forward_list>` 支持从任何单向可迭代范围获取 |\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++11             | `std::forward_list` 首次加入标准库；满足 `AllocatorAwareContainer`；提供单向 `before_begin`/`cbefore_begin`，并支持 `emplace_after`、`emplace_front`、`splice_after`、`remove_if` 等原地构造与节点迁移操作；比较运算符、`std::swap`、非成员 `erase`/`erase_if`（C++20 前）的基础定义齐备 | 以最小单向链表开销提供容器支持；可在指定位置后插入/拼接节点而不失效其他迭代器；适合流式写入场景 |\n",
    "| C++14             | 主要缺陷修复，无新增核心接口                                 | 行为和 API 与 C++11 一致                                     |\n",
    "| C++17             | 引入 `std::pmr::forward_list`（多态分配器别名）；类模板实参推导指引（CTAD）；允许以不完整类型实例化容器（`__cpp_lib_incomplete_container_elements`=201505L） | 容器可与 `pmr::memory_resource` 协作共享内存；列表初始化时可省略模板实参；可在头文件中声明包含前向声明类型的 `forward_list` 成员 |\n",
    "| C++20             | 要求 `Allocator::value_type` 必须等于 `T`（否则程序非良构）；新增非成员 `erase`/`erase_if` 用于按谓词删除元素；提供三路比较运算符 `<=>`（旧式关系运算移至 C++20 之前） | 强化分配器契约；批量删除操作更方便；与现代排序/比较基础设施兼容 |\n",
    "| C++23             | ranges 兼容性增强：新增 `assign_range`、`insert_range_after`、`prepend_range` 等接口，并支持 `std::ranges::to<std::forward_list>`；特性宏 `__cpp_lib_containers_ranges`=202202L | 与 ranges 框架无缝协作，从任意 range 构造或批量插入，避免中间容器 |\n",
    "| C++26（提案阶段） | 计划将全部成员函数 `constexpr` 化（特性宏 `__cpp_lib_constexpr_forward_list`=202502L），迭代器满足 `ConstexprIterator` 要求 | 汇编期算法可直接操作 `forward_list`（取决于实现支持），便于高级元编程场景 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::array<T, N>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/array.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 固定大小、连续存储；完全 `constexpr`；支持结构化绑定与 ranges |\n",
    "| 优点       | 零额外开销；编译期大小可优化；可直接传递给 C API             |\n",
    "| 缺陷       | 尺寸不可变；拷贝涉及全部元素                                 |\n",
    "| 时间复杂度 | 访问：O(1)；算法复杂度取决于元素操作                         |\n",
    "| 空间复杂度 | 固定 O(N)                                                    |\n",
    "| 常见互转   | 可使用 `std::to_array` (C++20) 从原生数组生成；区间构造或 ranges `to<vector>` 可转为 `vector`、`deque`; `std::span` 可零拷贝访问 |\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本  | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++11 | `std::array` 首次加入标准库，作为固定大小的聚合容器；提供 `get`、比较运算符、`std::swap`、`fill` 等基础接口 | 保留 C 风格数组的性能并补足容器能力（自带 `size`、迭代器等）；是 `ReversibleContainer`，但默认构造不为空；迭代器在生命周期内稳定 |\n",
    "| C++14 | 仅做缺陷修复，无新增核心特性                                 | API 与 C++11 一致                                            |\n",
    "| C++17 | 被正式归类为 `ContiguousContainer`；提供类模板实参推导指引（CTAD），可写 `std::array arr{1,2,3};` 自动推导元素类型与长度 | 标准保障其内存连续性，方便与 `span`/C API 协作；构造时无需显式模板实参 |\n",
    "| C++20 | 所有成员函数及迭代器 `constexpr` 化，迭代器满足 `contiguous_iterator` 要求；新增 `std::to_array` 将原生数组/`std::array` 包装为 `std::array`；比较运算符改为三路比较 `<=>`（旧式关系运算自 C++20 起移除） | 可在常量表达式中创建和操作 `std::array`；轻松从 C 风格数组生成 `std::array`；与 `<algorithm>`/排序设施的比较行为现代化 |\n",
    "| C++23 | 无额外核心特性（主要为缺陷修正），持续满足 ranges 概念（`borrowed_range`、`sized_range` 等） | 继续与 ranges、`std::span` 等设施无缝协作                    |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::basic_string<CharT>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/string/basic_string.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 连续字符缓冲，广泛采用 SSO；C++11 移动语义，C++20 `std::format`，C++23 `std::print`；提供 `pmr::basic_string` |\n",
    "| 优点       | 文本 API 丰富；小字符串性能好；与 C 风格字符串互操作         |\n",
    "| 缺陷       | SSO 容量实现差异；编码支持有限；中部修改成本高               |\n",
    "| 时间复杂度 | 访问：O(1)；尾部追加：摊还 O(1)；插删：O(n)；查找：O(n)      |\n",
    "| 空间复杂度 | O(n) + 可能的 SSO 缓冲                                       |\n",
    "| 常见互转   | 可通过构造/`assign` 与 `std::string_view`、`std::span<const CharT>` 互转；ranges `to<string>`；可用 `data()` 生成 `std::span`/C 字符串 |\n",
    "\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本                | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++11               | 为 `basic_string` 引入移动构造/移动赋值与 `shrink_to_fit`；新增数值转换族（`stoi`/`stol`/`stoll`、`stof`/`stod`/`stold`、`to_string`、`to_wstring`）；支持 UTF 宽字符别名 (`std::u16string`、`std::u32string`)；保证结尾存在空终止符且可将 `data()` 指针作为 C 字符串使用；成员 `front`/`back` 加入 | 大幅降低拷贝开销并方便与 C API 协作；提供统一的字符串↔数字转换接口；增强多语言字符处理能力 |\n",
    "| C++14               | 引入字符串字面量运算符 `\"\"s`（特性宏 `__cpp_lib_string_udls`=201304L） | 可直接写 `\"text\"s` 构造 `std::string`/`std::u16string` 等，改善字面量语义 |\n",
    "| C++17               | 新增 `std::pmr::basic_string` 别名，支持多态分配器；非 `const` `data()` 返回可写指针；提供 `operator basic_string_view()`，与 `std::string_view` 协作；类模板实参推导指引（CTAD）；`std::string` 等继续满足 `ContiguousContainer` | 容器可与 `pmr::memory_resource` 共享内存池；可无代价获取 `string_view` 视图；构造时可省略模板参数 |\n",
    "| C++20               | 所有成员函数 `constexpr` 化（宏 `__cpp_lib_constexpr_string`=201907L），迭代器满足 `contiguous_iterator`；加入 `starts_with`/`ends_with`（宏 `__cpp_lib_starts_ends_with`=201711L）；支持 `char8_t` 字符串别名 (`std::u8string`) 与相关字面量（宏 `__cpp_lib_char8_t`=201907L）；新增非成员 `erase`/`erase_if`（宏 `__cpp_lib_erase_if`=202002L）；提供三路比较 `<=>` | 字符串可在常量表达式中构造和操作；简化前缀/后缀检查；原生支持 UTF-8 字符类型；按谓词批量删除更方便；比较语义现代化 |\n",
    "| C++23               | 引入 `contains` 成员（宏 `__cpp_lib_string_contains`=202011L）；新增 ranges 友好接口：`assign_range`、`insert_range`、`append_range`、`replace_with_range`、`resize_and_overwrite`（宏 `__cpp_lib_containers_ranges`=202202L 与 `__cpp_lib_string_resize_and_overwrite`=202110L）；`std::ranges::to<std::basic_string>` 可直接构造字符串 | 与 ranges 框架深度整合，减少中间拷贝；`contains` 更易读；`resize_and_overwrite` 支持在已分配缓冲区内高效填充数据 |\n",
    "| Feature-test 宏汇总 | `__cpp_lib_string_udls`=201304L (C++14)<br>`__cpp_lib_starts_ends_with`=201711L (C++20)<br>`__cpp_lib_constexpr_string`=201907L (C++20)<br>`__cpp_lib_char8_t`=201907L (C++20)<br>`__cpp_lib_erase_if`=202002L (C++20)<br>`__cpp_lib_string_contains`=202011L (C++23)<br>`__cpp_lib_string_resize_and_overwrite`=202110L (C++23)<br>`__cpp_lib_containers_ranges`=202202L (C++23) |                                                              |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 关联容器（Associative Containers）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::map<Key, T>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/map.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 红黑树维护有序键值；C++11 `emplace`、移动；C++17 `try_emplace`、`node_handle`；C++20 `contains`；C++23 更广泛 `constexpr` |\n",
    "| 优点       | 查找/范围查询 O(log n)；迭代器稳定；支持异构查找 (`std::less<>`) |\n",
    "| 缺陷       | 节点内存高；不可随机访问；键值插入需分配                     |\n",
    "| 时间复杂度 | 插删/查找：O(log n)；遍历：O(n)                              |\n",
    "| 空间复杂度 | O(n) + 每节点 3 指针 + 颜色位                                |\n",
    "| 常见互转   | 可区间构造为 `std::map`/`std::multimap`/`std::vector`（排序）或 `std::flat_map`；`extract`/`merge` 与其他 map/unordered_map 交换节点；ranges `to<map>` 支持从已排序范围构建 |\n",
    "\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++11             | 继承通用容器升级：支持移动构造/移动赋值、`initializer_list` 构造/赋值、`emplace`/`emplace_hint`、`cbegin`/`cend`/`crbegin`/`crend`、`shrink_to_fit`（通过 `allocator_traits`）等；`map` 正式满足 `AllocatorAwareContainer` 要求 | 减少插入与扩容时的拷贝开销；常量迭代器接口让只读遍历更安全；可用花括号直接初始化键值对集合 |\n",
    "| C++14             | 标准库引入透明比较器（如 `std::less<void>`），`map` 的 `find`/`count`/`lower_bound`/`upper_bound`/`equal_range` 等在比较器具备 `is_transparent` 时支持异构查找；若未提供比较器，默认 `std::less<Key>` 可以改为 `std::less<>` 以启用该能力 | 可直接用不同但可比较的键类型查找（例如 `std::map<std::string, T>` 对 `const char*` 查找），减少中间对象构造 |\n",
    "| C++17             | 新增节点句柄接口：`extract`、`merge`、`node_type`、`insert_return_type`；提供 `try_emplace`、`insert_or_assign`；`insert`/`emplace` 可接收节点；加入 `std::pmr::map`（多态分配器别名）；类模板实参推导指引（CTAD）允许 `std::map m{std::pair{1,\"a\"}};` | 节点级操作实现零拷贝迁移/合并 map；在键存在时避免不必要的值构造，提升性能；PMR 版本便于自定义内存池；CTAD 简化声明 |\n",
    "| C++20             | 新增 `contains` 成员用于 O(log n) 存在性检测；提供非成员 `erase_if`（宏 `__cpp_lib_erase_if`=202002L）；比较运算采用三路比较 `<=>` 并移除旧式关系运算；要求 `Allocator::value_type` 与 `value_type` 相同；`map` 成员函数现均标记为 `constexpr`（但完整 constexpr map 需 C++26 才可用） | 查找接口更直观；可按谓词批量删除元素；比较语义与现代算法一致；更严格的分配器约束避免隐藏错误 |\n",
    "| C++23             | ranges 互操作增强：新增 `insert_range` 等接口（宏 `__cpp_lib_containers_ranges`=202202L）；`contains`、`equal_range` 等可直接与 ranges 组合；标准修订将节点句柄/异构查找的若干缺陷修复 | 能从任意 range 直接批量插入键值对，避免中间容器；ranges 管道写法更自然 |\n",
    "| C++26（提案阶段） | 计划引入全面 `constexpr` 化（宏 `__cpp_lib_constexpr_map`=202502L），迭代器满足 `ConstexprIterator`；`map` 可在常量表达式中执行插入、查找等操作 | 允许在编译期构建和查询平衡树结构，为元编程和 constexpr 数据结构打开可能（视编译器实现而定） |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::multimap<Key, T>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/multimap.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 红黑树允许重复键；同步获得 C++11–23 所有改进                 |\n",
    "| 优点       | 有序存储重复键；区间检索方便                                 |\n",
    "| 缺陷       | 单元素查找需遍历等值范围；节点开销与 `map` 相同              |\n",
    "| 时间复杂度 | 插删/查找：O(log n)；等值范围：O(log n + k)                  |\n",
    "| 空间复杂度 | O(n) + 节点指针开销                                          |\n",
    "| 常见互转   | 可用区间构造转换为 `map`（需去重）、`flat_map`、`vector`；`extract`/`merge` 可与 `map` 互换节点 |\n",
    "\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++11             | 泛型容器整体升级：支持移动构造/移动赋值、`initializer_list` 构造与赋值、`emplace`/`emplace_hint`、`cbegin`/`cend`/`crbegin`/`crend` 等；满足 `AllocatorAwareContainer` 规范 | 减少插入/复制开销，提供 const 迭代器接口，可用花括号直接初始化键值对序列 |\n",
    "| C++14             | 透明比较器（如 `std::less<>`）可启用异构查找：`find`/`count`/`lower_bound`/`upper_bound`/`equal_range` 在比较器具备 `is_transparent` 时可接受不同但可比较的键类型 | 允许使用 `const char*` 查找 `std::multimap<std::string, T>` 等，避免构造临时键对象 |\n",
    "| C++17             | 引入节点句柄接口：`extract`、`merge`、`node_type`；`insert` 可直接接收节点；提供 `std::pmr::multimap` 多态分配器别名；类模板实参推导指引（CTAD） | 支持零拷贝迁移/合并树节点；可与 PMR 内存资源共享；声明时可省略模板参数 |\n",
    "| C++20             | 新增 `contains` 成员用于 O(log n) 存在性检测；非成员 `erase_if`（宏 `__cpp_lib_erase_if`=202002L）；比较运算统一为三路比较 `<=>` 并移除旧式关系运算；要求 `Allocator::value_type` 与 `value_type` 一致；成员函数均标记为 `constexpr`（完整 constexpr 支持待 C++26） | 接口更直观现代；可按谓词批量删除元素；比较语义与 `<algorithm>` 等设施兼容；更严格的分配器约束防止隐患 |\n",
    "| C++23             | ranges 支持增强：`insert_range` 等接口（宏 `__cpp_lib_containers_ranges`=202202L），并修订节点句柄/异构查找的缺陷 | 可从任意 range 批量插入键值对，简化与 ranges 管道组合；行为更一致 |\n",
    "| C++26（提案阶段） | 计划实现全面 `constexpr` 化（宏 `__cpp_lib_constexpr_multimap`=202502L，名称化同类提案），迭代器满足 `ConstexprIterator` 要求 | 若实现支持，可在编译期构建和操作多重映射，利于 constexpr 配置与元编程场景 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::set<Key>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/set.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 红黑树仅存键；C++14 引入透明比较，C++17 `node_handle`，C++23 `constexpr` |\n",
    "| 优点       | 自动去重；升序迭代；查找 O(log n)                            |\n",
    "| 缺陷       | 不支持随机访问；元素键不可修改；节点开销高                   |\n",
    "| 时间复杂度 | 插删/查找：O(log n)                                          |\n",
    "| 空间复杂度 | O(n) + 每节点 3 指针                                         |\n",
    "| 常见互转   | 可区间构造转换为 `vector`（保持排序）、`flat_set`；与 `multiset`/`map` 使用 `extract`/`merge` 转换；ranges `to<set>` 支持 |\n",
    "\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++11             | 泛型容器升级：支持移动构造/移动赋值、`initializer_list` 构造与赋值、`emplace`/`emplace_hint`、`cbegin`/`cend`/`crbegin`/`crend` 等；满足 `AllocatorAwareContainer` 要求 | 减少节点插入时的拷贝开销；可用花括号直接初始化集合；常量迭代器接口让只读遍历更安全 |\n",
    "| C++14             | 借助透明比较器（如 `std::less<>`），`find`/`count`/`lower_bound`/`upper_bound`/`equal_range` 可在比较器具备 `is_transparent` 时执行异构查找 | 允许用可比较的不同类型（如 `const char*`）搜索 `std::set<std::string>`，避免创建临时对象 |\n",
    "| C++17             | 节点句柄 API：`extract`、`merge`、`node_type`；`insert` 可接受节点；`std::pmr::set` 别名引入；类模板实参推导指引（CTAD）可写 `std::set s{1,2,3};` | 可零拷贝迁移/合并节点；易于与多态内存资源协作；初始化更简洁  |\n",
    "| C++20             | 新增 `contains` 成员进行 O(log n) 存在性检查；非成员 `erase_if`（宏 `__cpp_lib_erase_if`=202002L）；比较运算采用 `<=>` 并移除旧式关系运算；要求 `Allocator::value_type` 与 `value_type` 相同；成员函数标记为 `constexpr`（完整 constexpr 支持待 C++26） | 接口现代化并与 `<algorithm>` 协作更好；可按谓词批量删除元素；分配器约束更严格以避免未定义行为 |\n",
    "| C++23             | ranges 互操作增强：`insert_range` 等接口（宏 `__cpp_lib_containers_ranges`=202202L）；修订节点句柄与异构查找的缺陷 | 可直接从任意 range 批量插入元素，简化与 ranges 管道的组合；行为更一致 |\n",
    "| C++26（提案阶段） | 计划支持完全 `constexpr`（宏 `__cpp_lib_constexpr_set`=202502L），迭代器满足 `ConstexprIterator` | 若实现支持，可在编译期构建/查询平衡树集合，拓展 constexpr 数据结构的可能性 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::set<Key>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/set.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 红黑树仅存键；C++14 引入透明比较，C++17 `node_handle`，C++23 `constexpr` |\n",
    "| 优点       | 自动去重；升序迭代；查找 O(log n)                            |\n",
    "| 缺陷       | 不支持随机访问；元素键不可修改；节点开销高                   |\n",
    "| 时间复杂度 | 插删/查找：O(log n)                                          |\n",
    "| 空间复杂度 | O(n) + 每节点 3 指针                                         |\n",
    "| 常见互转   | 可区间构造转换为 `vector`（保持排序）、`flat_set`；与 `multiset`/`map` 使用 `extract`/`merge` 转换；ranges `to<set>` 支持 |\n",
    "\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++11             | 泛型容器升级：支持移动构造/移动赋值、`initializer_list` 构造与赋值、`emplace`/`emplace_hint`、`cbegin`/`cend`/`crbegin`/`crend` 等；满足 `AllocatorAwareContainer` 要求 | 减少节点插入时的拷贝开销；可用花括号直接初始化集合；常量迭代器接口让只读遍历更安全 |\n",
    "| C++14             | 借助透明比较器（如 `std::less<>`），`find`/`count`/`lower_bound`/`upper_bound`/`equal_range` 可在比较器具备 `is_transparent` 时执行异构查找 | 允许用可比较的不同类型（如 `const char*`）搜索 `std::set<std::string>`，避免创建临时对象 |\n",
    "| C++17             | 节点句柄 API：`extract`、`merge`、`node_type`；`insert` 可接受节点；`std::pmr::set` 别名引入；类模板实参推导指引（CTAD）可写 `std::set s{1,2,3};` | 可零拷贝迁移/合并节点；易于与多态内存资源协作；初始化更简洁  |\n",
    "| C++20             | 新增 `contains` 成员进行 O(log n) 存在性检查；非成员 `erase_if`（宏 `__cpp_lib_erase_if`=202002L）；比较运算采用 `<=>` 并移除旧式关系运算；要求 `Allocator::value_type` 与 `value_type` 相同；成员函数标记为 `constexpr`（完整 constexpr 支持待 C++26） | 接口现代化并与 `<algorithm>` 协作更好；可按谓词批量删除元素；分配器约束更严格以避免未定义行为 |\n",
    "| C++23             | ranges 互操作增强：`insert_range` 等接口（宏 `__cpp_lib_containers_ranges`=202202L）；修订节点句柄与异构查找的缺陷 | 可直接从任意 range 批量插入元素，简化与 ranges 管道的组合；行为更一致 |\n",
    "| C++26（提案阶段） | 计划支持完全 `constexpr`（宏 `__cpp_lib_constexpr_set`=202502L），迭代器满足 `ConstexprIterator` | 若实现支持，可在编译期构建/查询平衡树集合，拓展 constexpr 数据结构的可能性 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::multiset<Key>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/multiset.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 红黑树允许键重复；现代特性与 `set` 同步                      |\n",
    "| 优点       | 维护有序多重集合；区间检索方便                               |\n",
    "| 缺陷       | 查找单元素需遍历等值范围；内存开销与 `set` 相同              |\n",
    "| 时间复杂度 | 插删/查找：O(log n)；等值范围：O(log n + k)                  |\n",
    "| 空间复杂度 | O(n) + 节点指针开销                                          |\n",
    "| 常见互转   | 可区间构造为 `set`（需去重）或 `vector`；`extract/merge` 与 `set`、`map` 互联；ranges `to<multiset>` 支持 |\n",
    "\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++11             | 泛型容器升级：支持移动构造/移动赋值、`initializer_list` 构造与赋值、`emplace`/`emplace_hint`、`cbegin`/`cend`/`crbegin`/`crend` 等；满足 `AllocatorAwareContainer` 要求 | 减少节点插入时的拷贝开销；可用花括号直接初始化集合；常量迭代器接口让只读遍历更安全 |\n",
    "| C++14             | 借助透明比较器（如 `std::less<>`），`find`/`count`/`lower_bound`/`upper_bound`/`equal_range` 可在比较器具备 `is_transparent` 时执行异构查找 | 允许用可比较的不同类型（如 `const char*`）搜索 `std::set<std::string>`，避免创建临时对象 |\n",
    "| C++17             | 节点句柄 API：`extract`、`merge`、`node_type`；`insert` 可接受节点；`std::pmr::set` 别名引入；类模板实参推导指引（CTAD）可写 `std::set s{1,2,3};` | 可零拷贝迁移/合并节点；易于与多态内存资源协作；初始化更简洁  |\n",
    "| C++20             | 新增 `contains` 成员进行 O(log n) 存在性检查；非成员 `erase_if`（宏 `__cpp_lib_erase_if`=202002L）；比较运算采用 `<=>` 并移除旧式关系运算；要求 `Allocator::value_type` 与 `value_type` 相同；成员函数标记为 `constexpr`（完整 constexpr 支持待 C++26） | 接口现代化并与 `<algorithm>` 协作更好；可按谓词批量删除元素；分配器约束更严格以避免未定义行为 |\n",
    "| C++23             | ranges 互操作增强：`insert_range` 等接口（宏 `__cpp_lib_containers_ranges`=202202L）；修订节点句柄与异构查找的缺陷 | 可直接从任意 range 批量插入元素，简化与 ranges 管道的组合；行为更一致 |\n",
    "| C++26（提案阶段） | 计划支持完全 `constexpr`（宏 `__cpp_lib_constexpr_set`=202502L），迭代器满足 `ConstexprIterator` | 若实现支持，可在编译期构建/查询平衡树集合，拓展 constexpr 数据结构的可能性 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::flat_map<Key, T>`（C++23）\n",
    "\n",
    "- https://www.en.cppreference.com/w/cpp/container/flat_map.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 排序 `std::vector<std::pair<>>`；查找用二分；可与自定义比较器结合 |\n",
    "| 优点       | 连续内存、缓存友好；遍历快；构建后查找 O(log n)              |\n",
    "| 缺陷       | 插删 O(n)；迭代器在插入时失效；不适合频繁更新                |\n",
    "| 时间复杂度 | 查找：O(log n)；插删：O(n)                                   |\n",
    "| 空间复杂度 | O(n) 连续存储                                                |\n",
    "| 常见互转   | 可通过区间构造从 `map`/`vector`/`ranges::sort` 后的任何范围构建；可 `ranges::to<flat_map>`；可用 `assign`/`insert` 接受 `map` 节点（复制） |\n",
    "\n",
    "> 与 `std::map `相比，`std::flat_map `并非万能替身，但在“小规模、高访问频率、读多写少”的场景下能显著提升性能与简化代码，这正是它被纳入标准库的核心动机\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++23             | 首次引入 `std::flat_map`（特性宏 `__cpp_lib_flat_map`=202207L）；作为基于顺序容器的关联容器适配器，默认为 `std::vector` 存放键和值；提供 `sorted_unique`/`sorted_unique_t` 标签用于跳过排序与去重；支持节点外的所有唯一键操作（`insert`、`try_emplace`、`insert_or_assign` 等），并暴露底层容器访问 (`keys()`/`values()`、`extract`/`replace`)；提供同标准顺序容器一致的迭代器（随机访问）、`erase_if`、`operator<=>`、`std::swap` | 通过缓存友好的连续存储实现更好的遍历性能与空间局部性；可在已排序唯一的输入上高效构建；允许直接操作底层容器实现批量初始化或自定义存储策略；线性插入/删除复杂度换取更快的查找 |\n",
    "| C++26（提案阶段） | 计划实现全面 `constexpr` 化（特性宏 `__cpp_lib_constexpr_flat_map`=202502L），迭代器满足 `ConstexprIterator` 要求 | 若实现支持，可在编译期构建和查询扁平映射，为 constexpr 配置表、查找表等提供便利 |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// https://godbolt.org/z/efqh99W64\n",
    "\n",
    "#include <flat_map>\n",
    "#include <iostream>\n",
    "#include <ranges>\n",
    "#include <vector>\n",
    "\n",
    "int main() {\n",
    "    using registry = std::flat_map<int, std::string>;\n",
    "\n",
    "    // 1. 直接用 initializer_list 构造（会自动排序和去重）\n",
    "    registry commands{\n",
    "        {200, \"OK\"},\n",
    "        {404, \"Not Found\"},\n",
    "        {500, \"Internal Server Error\"},\n",
    "    };\n",
    "\n",
    "    // 2. try_emplace：读多写少场景下常用的惰性构造\n",
    "    commands.try_emplace(301, \"Moved Permanently\");\n",
    "    commands.try_emplace(404, \"Duplicate, will be ignored\");\n",
    "\n",
    "    // 3. 查找和下界查询与 std::map 接口一致\n",
    "    if (auto it = commands.find(200); it != commands.end()) {\n",
    "        std::cout << it->first << \" -> \" << it->second << '\\n';\n",
    "    }\n",
    "\n",
    "    auto next = commands.lower_bound(450);\n",
    "    if (next != commands.end()) {\n",
    "        std::cout << \"First status >=450 is \" << next->first << '\\n';\n",
    "    }\n",
    "\n",
    "    // 4. 使用 sorted_unique 标签接管已排序的数据，避免额外排序/去重开销\n",
    "    std::vector<int> keys   = {10, 20, 30};\n",
    "    std::vector<std::string> values = {\"alpha\", \"beta\", \"gamma\"};\n",
    "    registry prebuilt(std::from_range, std::sorted_unique, keys, values);\n",
    "\n",
    "    // 5. ranges 管道：批量插入\n",
    "    auto new_entries = std::views::zip(\n",
    "        std::array{600, 503, 403},\n",
    "        std::array{\"Service Unavailable\", \"Bad Gateway\", \"Forbidden\"}\n",
    "    );\n",
    "\n",
    "    commands.insert_range(new_entries); // 自动排序合并\n",
    "\n",
    "    // 6. 查看底层连续数组，适合与 SIMD/批处理结合\n",
    "    const auto& raw_keys = commands.keys();\n",
    "    const auto& raw_vals = commands.values();\n",
    "    std::cout << \"Keys are stored contiguously: \";\n",
    "    for (int key : raw_keys) std::cout << key << ' ';\n",
    "    std::cout << '\\n';\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::flat_set<Key>`（C++23）\n",
    "\n",
    "- https://www.en.cppreference.com/w/cpp/container/flat_set.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 排序 `std::vector` 存键；二分查找定位                        |\n",
    "| 优点       | 内存紧凑、遍历快；与 `flat_map` 同步特性                     |\n",
    "| 缺陷       | 插删 O(n)；迭代器在插入时失效                                |\n",
    "| 时间复杂度 | 查找：O(log n)；插删：O(n)                                   |\n",
    "| 空间复杂度 | O(n) 连续存储                                                |\n",
    "| 常见互转   | 可从 `set`/`multiset`/`vector` 通过排序后区间构造；`ranges::to<flat_set>`；可用 `insert` 接受任意可排序范围 |\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++23             | 首次引入 `std::flat_set`（特性宏 `__cpp_lib_flat_set`=202207L）；提供基于顺序容器（默认 `std::vector`）的集合适配器；支持 `sorted_unique`/`sorted_unique_t` 标签跳过排序与去重；暴露底层容器访问（`container()`、`extract`、`replace`），并提供随机访问迭代器、`erase_if`、`operator<=>`、`std::swap` 等现代接口 | 连续存储显著提升遍历与查找时的缓存局部性；可利用已排序唯一的数据高效构造；易于批量初始化和与 `ranges` 协作；以线性插入/删除复杂度换取读多写少场景的性能优势 |\n",
    "| C++26（提案阶段） | 计划实现全面 `constexpr` 化（特性宏 `__cpp_lib_constexpr_flat_set`=202502L），迭代器满足 `ConstexprIterator` 要求 | 若实现支持，可在编译期构建和查询扁平集合，支持更多 `constexpr` 查找表或配置数据场景 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 无序容器（Unordered Containers）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::unordered_map<Key, T>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/unordered_map.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 桶式哈希表（链式节点/开放寻址视实现）；C++11 标准化，C++17 `extract/merge`，C++20 `contains`/`erase_if`，C++23 `constexpr` 化 |\n",
    "| 优点       | 插删查平均 O(1)；节点句柄可在 map/unordered_map 间迁移；高度可定制哈希 |\n",
    "| 缺陷       | 最坏 O(n)；rehash 成本高且迭代器失效；遍历顺序不稳定         |\n",
    "| 时间复杂度 | 插删查：均摊 O(1)，最坏 O(n)；rehash：O(n)                   |\n",
    "| 空间复杂度 | O(n) 数据 + 桶数组开销（负载因子影响）                       |\n",
    "| 常见互转   | `extract`/`merge` 与 `map` 互转节点；区间构造与 ranges `to<unordered_map>` 从 `vector`、`list`、`map` 等构建；可用 `reserve` 优化批量转换 |\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++11             | 首次引入 `std::unordered_map`，提供哈希表语义的关联容器；具备节点型接口（`insert`、`emplace`、`erase` 等）与桶管理、哈希策略接口，满足 `UnorderedAssociativeContainer` 与 `AllocatorAwareContainer` 要求。 | 面向平均 O(1) 查找/插入/删除的场景，相比有序容器牺牲顺序换取常数时间；用户需关注哈希函数与装载因子以控制性能。 |\n",
    "| C++14             | 增补异构查找支持：当 `Hash`、`KeyEqual` 拥有 `is_transparent` 成员时，`find`/`count`/`equal_range`/`erase` 可接受与 `key_type` 可比较但不同的键类型。 | 避免构造临时键（例如 `std::string` 对照 `std::string_view`），在高频查找中显著降低分配与拷贝成本。 |\n",
    "| C++17             | 新增节点句柄与批量操作：`extract`/`merge`、`node_type`、`insert_return_type`；引入 `try_emplace`、`insert_or_assign`；增加 `pmr::unordered_map` 别名；改进 `emplace_hint` 等插入接口。 | 可无拷贝地迁移节点并在容器间合并；`try_emplace` 避免不必要的值构造；PMR 支持便于自定义内存资源与短生命周期分配；接口更贴近实际工程需求。 |\n",
    "| C++20             | 增补现代化接口：`contains` 常量时间存在性检测；非成员 `erase_if`；删去显式 `operator!=`（由 `operator==` 推导）；完善 constexpr 约束（但整体 constexpr 仍受分配限制）。 | 阅读性更好（`contains`）；可按谓词批量删除；接口行为与其他标准容器保持一致；为未来 constexpr 化奠定规范基础。 |\n",
    "| C++23             | Ranges 生态支持（特性宏 `__cpp_lib_containers_ranges`=202202L）：`insert_range`、`from_range` 构造/赋值、`in_node_handle_type`/`node_type` 的 ranges 兼容；改进 `merge`、`erase` 等缺陷。 | 可直接从任意 ranges（含惰性视图）构造与插入，易于与管道算法衔接；节点 API 更稳健，便于泛型库复用；提升批量导入数据的易用性。 |\n",
    "| C++26（提案阶段） | 计划提供全面 `constexpr` 支持（特性宏 `__cpp_lib_constexpr_unordered_map`=202502L），迭代器满足 `ConstexprIterator`；允许在常量表达式中执行哈希表操作（需实现方提供 constexpr 哈希等支持）。 | 一旦实现落地，可在编译期构建哈希查找表并执行查询/插入，适用于 `constexpr` 配置与元编程；同时为资源受限环境提供零运行期开销的查找结构。 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::unordered_set<Key>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/unordered_set.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 同 `unordered_map`，仅存键；支持透明哈希/比较                |\n",
    "| 优点       | membership 测试均摊 O(1)；可按需选择哈希策略                 |\n",
    "| 缺陷       | 不保持顺序；rehash 代价高；最坏 O(n)                         |\n",
    "| 时间复杂度 | 插删查：均摊 O(1)；rehash：O(n)                              |\n",
    "| 空间复杂度 | O(n) + 桶数组开销                                            |\n",
    "| 常见互转   | 可区间构造自 `vector`、`set`、`span`；`extract/merge` 与 `unordered_multiset`、`set` 互换；ranges `to<unordered_set>` 支持 |\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++11             | 首次引入 `std::unordered_set`，提供基于哈希表的唯一键集合；具备桶接口、哈希策略、`find`/`insert`/`erase` 等节点操作；满足 `UnorderedAssociativeContainer` 与 `AllocatorAwareContainer` 要求。 | 适用于平均 O(1) 查找/插入/删除的场景，牺牲有序性换取常数时间性能；用户需要关注哈希函数质量与装载因子以维持性能。 |\n",
    "| C++14             | 引入异构查找支持：当 `Hash`、`KeyEqual` 声明 `is_transparent` 时，`find`、`count`、`equal_range`、`erase` 可接受与 `key_type` 可比较但类型不同的键。 | 避免构造临时键（如 `std::string` vs. `std::string_view`），显著降低高频查找时的分配与拷贝开销，提升实用性。 |\n",
    "| C++17             | 增补节点句柄生态：`extract`/`merge`、`node_type`、`insert_return_type`；新增 `pmr::unordered_set` 别名；改进 `emplace_hint` 等插入接口。 | 支持无拷贝地迁移节点、跨容器合并；PMR 版本便于控制内存分配策略，适合自定义内存资源或短生命周期分配；插入语义更灵活。 |\n",
    "| C++20             | 新增现代化接口：`contains` 常量时间存在性检测；非成员 `erase_if`；移除显式 `operator!=`（由 `operator==` 推导）；完善 constexpr 约束（仍受动态分配限制）。 | API 可读性更好（`contains`）；按谓词批量删除更简便；接口与其他容器保持一致；为未来 constexpr 化做准备。 |\n",
    "| C++23             | 引入 ranges 支持（特性宏 `__cpp_lib_containers_ranges`=202202L）：提供 `insert_range`、`from_range` 构造/赋值；使节点句柄与 ranges 更好协作，并修复 `merge`、`erase` 等角落行为。 | 可直接从 ranges 或惰性视图构造/批量插入；易与 `views::filter`、`views::transform` 等组合使用；提升批量数据导入与泛型算法的便利性。 |\n",
    "| C++26（提案阶段） | 计划提供全面 `constexpr` 支持（特性宏 `__cpp_lib_constexpr_unordered_set`=202502L），迭代器满足 `ConstexprIterator` 要求，可在常量表达式中执行哈希表操作（需实现方提供 constexpr 兼容的哈希/比较器等）。 | 如实现到位，可在编译期构建并查询哈希集合，支持 constexpr 查找表、元编程等零运行期开销场景；对嵌入式或高性能配置数据尤为有利。 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 容器适配器（Container Adaptors）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C++ 容器适配器（Container Adapters）是基于现有标准容器（如 `std::deque`、`std::vector`、`std::list` 等）包装出的“接口限定版”容器类型。它们通过限制或重新定义操作接口，使使用者只需关注特定的抽象数据结构行为，而无需关心底层容器的实现细节。\n",
    "\n",
    "- 为什么需要容器适配器\n",
    "\n",
    "1. **抽象与代码清晰度**\n",
    "    通过提供特定的接口（例如栈的后进先出、队列的先进先出），让代码更贴合逻辑描述，便于理解和维护。\n",
    "2. **隐藏实现细节**\n",
    "    底层容器的选择可以在实现时决定，使用者只需面向接口编程，提高灵活性。例如 `std::stack` 可以基于 `std::deque` 或 `std::vector` 构建。\n",
    "3. **减少错误与提升安全性**\n",
    "    限制只暴露与目标抽象相关的方法（如 `std::stack` 限制在 push/pop/top），避免误用底层容器不必要的成员函数。\n",
    "4. **复用现有容器特性**\n",
    "    适配器并未重新实现存储，而是复用底层容器的高效实现，保持性能优势。\n",
    "\n",
    "- 容器适配器对比表\n",
    "\n",
    "| 适配器                   | 默认底层容器  | 可选底层容器               | 访问接口                        | 主要操作                     | 适用场景                                                     |\n",
    "| ------------------------ | ------------- | -------------------------- | ------------------------------- | ---------------------------- | ------------------------------------------------------------ |\n",
    "| `std::stack<T>`          | `std::deque`  | `std::vector`、`std::list` | `top()`                         | `push()`、`pop()`、`top()`   | 实现后进先出（LIFO）的场景，例如函数调用栈、括号匹配等       |\n",
    "| `std::queue<T>`          | `std::deque`  | `std::list`                | `front()`、`back()`             | `push()`、`pop()`、`front()` | 实现先进先出（FIFO）的场景，例如任务排队、消息队列           |\n",
    "| `std::priority_queue<T>` | `std::vector` | `std::deque`（极少使用）   | `top()`（返回优先级最高的元素） | `push()`、`pop()`、`top()`   | 需要按优先级调度的场景，例如事件调度、任务调度、Dijkstra 算法等 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::stack<T, Container>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/stack.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 适配器默认基于 `deque`；C++11 起支持移动、`emplace`；底层容器可替换为 `vector`/`list` 等 |\n",
    "| 优点       | LIFO 接口简单；性能取决于底层容器，通常 O(1)                 |\n",
    "| 缺陷       | 无遍历/迭代器；功能受限                                      |\n",
    "| 时间复杂度 | `push/pop/top`：O(1)（取决于底层容器）                       |\n",
    "| 空间复杂度 | 与底层容器一致                                               |\n",
    "| 常见互转   | 通过 `container_type` 构造/取出底层容器后可转换为 `vector`、`deque` 等；可直接用底层容器区间构造新的 `stack` |\n",
    "\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++98             | 引入容器适配器 `std::stack`，默认基于 `std::deque`，提供 LIFO 接口（`push`/`pop`/`top` 等）。 | 以最小接口封装顺序容器，实现常量时间的入栈/出栈操作；可选择不同底层容器以满足自定义性能或内存需求。 |\n",
    "| C++11             | 新增 `emplace` 在栈顶原位构造元素；提供 `swap` 成员与非成员；加入 `std::uses_allocator<std::stack>` 特化。 | 避免临时对象构造与复制，提升性能；与其他标准容器保持一致的交换与分配器支持，便于泛型代码与自定义 Allocator。 |\n",
    "| C++17             | 提供类模板参数推导指引（CTAD）。                             | 允许通过构造函数参数推导模板参数，降低样板代码。             |\n",
    "| C++20             | 引入默认的三向比较 `operator<=>`，实现全套比较运算符。       | 在比较两个栈时拥有标准化比较语义，配合 `<=>` 写法更简洁。    |\n",
    "| C++23             | Ranges 支持（特性宏 `__cpp_lib_containers_ranges`=202202L）：新增 `push_range`、范围构造与赋值；提供 `std::formatter<std::stack>`。 | 可直接将 ranges（含惰性视图）推入栈顶，提升与 ranges 管道组合时的易用性；标准化格式化支持，便于与 `std::format`/`std::print` 协同。 |\n",
    "| C++26（提案阶段） | 计划全面 `constexpr` 化（特性宏 `__cpp_lib_constexpr_stack`=202502L），所有操作可在常量表达式中执行；对迭代器无要求更新（作为适配器仍依赖底层容器的 constexpr 能力）。 | 若实现方完成支持，可在编译期构建与操作栈，适用于 constexpr 算法与查表场景；需底层容器也支持 constexpr 分配/释放，否则整体仍受限。 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::queue<T, Container>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/queue.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 适配器默认使用 `deque`；支持移动/`emplace`；可用 `list` 等替换 |\n",
    "| 优点       | FIFO 行为明确；接口简单                                      |\n",
    "| 缺陷       | 无随机访问或遍历；批量操作需自定义                           |\n",
    "| 时间复杂度 | `push/pop/front/back`：O(1)（依赖底层容器）                  |\n",
    "| 空间复杂度 | 与底层容器一致                                               |\n",
    "| 常见互转   | 通过底层 `container` 构造转换至 `deque`、`list`；ranges 可先收集为 `vector` 再构造 `queue` |\n",
    "\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++98             | 引入容器适配器 `std::queue`，默认基于 `std::deque`，提供 FIFO 接口（`push`/`pop`/`front`/`back`/`size` 等）。 | 以最小接口封装顺序容器，保证入队/出队的常量时间复杂度；可按需切换底层容器（如 `std::list`）以平衡内存布局和性能。 |\n",
    "| C++11             | 新增 `emplace` 在队尾原位构造元素；提供成员/非成员 `swap`；加入 `std::uses_allocator<std::queue>` 特化。 | 避免额外的临时对象构造与复制；交换操作与自定义分配器支持与其他容器保持一致，更利于泛型代码复用。 |\n",
    "| C++17             | 提供类模板参数推导指引（CTAD）。                             | 可通过构造函数参数自动推导模板参数，减少显式类型书写，增强易用性。 |\n",
    "| C++20             | 引入默认的三向比较 `operator<=>`，自动生成全套比较运算符。   | 队列之间比较语义标准化，与更丰富的比较表达式兼容；使用 `<=>` 更简洁。 |\n",
    "| C++23             | Ranges 支持（特性宏 `__cpp_lib_containers_ranges`=202202L）：新增 `push_range` 及基于 ranges 的构造/赋值；标准化 `std::formatter<std::queue>`。 | 可直接从 ranges（含惰性视图）批量入队，与管道算法无缝衔接；拥有 `std::format`/`std::print` 支持，调试与日志输出更方便。 |\n",
    "| C++26（提案阶段） | 计划实现全面 `constexpr` 化（特性宏 `__cpp_lib_constexpr_queue`=202502L），所有操作可在常量表达式中执行（前提是底层容器也具备相应 constexpr 能力）。 | 若实现到位，可在编译期构建并操作队列，适用于 constexpr 算法和查表场景；对底层容器的 constexpr 支持提出更高要求，尤其是动态分配的释放需在同一常量求值中完成。 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::priority_queue<T, Container, Compare>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/priority_queue.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 基于 `vector` + 堆算法 (`push_heap`/`pop_heap`)；C++11 起支持移动/`emplace`；C++20 正推进 `constexpr` |\n",
    "| 优点       | `top` O(1) 获取极值；`push/pop` 维持堆 O(log n)              |\n",
    "| 缺陷       | 无顺序遍历；批量删除复杂                                     |\n",
    "| 时间复杂度 | `push/pop`：O(log n)；`top`：O(1)                            |\n",
    "| 空间复杂度 | O(n) 连续存储                                                |\n",
    "| 常见互转   | 通过 `container_type` (`vector`) 可与 `vector`、`deque` 互转；从任何范围可使用区间构造并自动堆化；可与 `std::ranges::to<vector>` 后调用 `make_heap` 转换 |\n",
    "\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++98             | 引入容器适配器 `std::priority_queue`，默认使用 `std::vector` 与 `std::less`，封装堆操作提供最大堆（默认）语义。 | 将堆相关算法以面向对象方式封装，提供 `top`/`push`/`pop` 等接口，保证 O(log N) 插入与删除，O(1) 获取极值。 |\n",
    "| C++11             | 增加 `emplace` 原位构造元素；提供成员/非成员 `swap`；加入 `std::uses_allocator<std::priority_queue>` 特化。 | 避免中间对象构造与复制；与其他容器一致的交换与自定义分配器支持，提升泛型与性能表现。 |\n",
    "| C++17             | 提供类模板参数推导指引（CTAD）。                             | 允许通过构造函数参数推导模板参数，简化实例化代码，便于自定义比较器或底层容器时的书写。 |\n",
    "| C++20             | 无新的专属接口变更（保持与以往版本兼容）。                   | 仍依赖 C++17 接口集，可继续利用堆语义；标准的整体改进（如 ranges、constexpr）尚未涉及该适配器。 |\n",
    "| C++23             | Ranges 支持（特性宏 `__cpp_lib_containers_ranges`=202202L）：新增 `push_range` 以及 ranges 构造/赋值；提供 `std::formatter<std::priority_queue>`。 | 可直接从 ranges（包括惰性视图）批量入队并维持堆性质，利于与 `views::transform`/`filter` 等组合；标准化格式化支持，方便使用 `std::format`/`std::print` 输出调试信息。 |\n",
    "| C++26（提案阶段） | 计划全面 `constexpr` 化（共用特性宏 `__cpp_lib_constexpr_queue`=202502L），所有接口可在常量表达式中使用（需底层容器与比较器也支持 constexpr）。 | 若实现完成，可在编译期构建并操作优先队列，实现零运行期开销的配置或查表；但仍受限于底层容器的 constexpr 分配能力及比较器是否可在 constexpr 环境中调用。 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 视图与轻量容器（Views & Non-owning）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::string_view`\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 指针+长度的非拥有视图；C++17 引入，`constexpr` 友好；支持 hetero 查找 |\n",
    "| 优点       | 零拷贝子串；常量时间切片；易与 `string` 交互                 |\n",
    "| 缺陷       | 生命周期依赖底层字符串；只读；编码一致性需自管               |\n",
    "| 时间复杂度 | 访问：O(1)；查找：O(n)                                       |\n",
    "| 空间复杂度 | O(1)（指针 + 长度）                                          |\n",
    "| 常见互转   | 可从 `string`/`char*`/`vector<char>`/`array<char>` 建立；可用于构造 `string`、`vector<char>`；`std::span<const char>` 与其互转需借助构造函数 |\n",
    "\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本  | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++17 | 引入 `std::basic_string_view` 及别名（`std::string_view` 等），提供对常量字符序列的零拷贝视图；支持标准字符串查找/比较接口与 `operator\"\"sv` 字面量；满足 `TriviallyCopyable` 要求；自带哈希特化（同版本）。 | 让 API 能以引用语义传递字符串，避免临时分配与复制；便捷的 `\"text\"sv` 字面量与哈希支持提升在容器中的使用体验；要求调用者确保底层数据在视图生命周期内有效。 |\n",
    "| C++20 | 迭代器满足 `ConstexprIterator` 与 `contiguous_iterator`；新增 `starts_with`、`ends_with`；将 `std::basic_string_view` 标记为 `ranges::view` 与 `ranges::borrowed_range`；推导指引（CTAD）可用。 | 可在 constexpr 环境中遍历视图，并与 ranges 算法无缝结合；新增前缀/后缀判断接口提高常见操作的可读性；ranges 适配使其可作为视图来源或目标。 |\n",
    "| C++23 | 新增 `contains` 与 `std::formatter<std::basic_string_view>`（通过 `std::format` 支持）；正式要求所有特化为 `TriviallyCopyable`；常用别名（`std::u8string_view` 等）在标准文档中集中列出。 | `contains` 提供直观的子串检测；格式化支持提升与现代输出/日志 API 的集成；`TriviallyCopyable` 的标准化要求确保跨实现一致的 ABI 与性能特征。 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::span<T>`\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/span.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 指针+长度视图（可选动态范围）；C++20 引入；支持 `constexpr`、多维扩展 |\n",
    "| 优点       | 零拷贝访问数组或容器；安全边界检查（调试版）；与 ranges 协同 |\n",
    "| 缺陷       | 不拥有数据；长度固定；仅线性访问                             |\n",
    "| 时间复杂度 | 访问：O(1)；遍历：O(n)                                       |\n",
    "| 空间复杂度 | O(1)（指针 + 长度）                                          |\n",
    "| 常见互转   | 可从 `vector`、`array`、原生数组、`string`（`span<const char>`）生成；可用于构造 `vector`、`array`（需复制）；`mdspan` 可由 `span` 派生多维视图 |\n",
    "\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++20             | 首次引入 `std::span`，支持静态/动态 extent 的连续内存视图；迭代器满足 `contiguous_iterator` 要求，可与 ranges 生态协作；提供 `as_bytes` / `as_writable_bytes`。 | 为数组、`std::array`、`std::vector` 等提供零拷贝、边界已知的统一视图；作为 ranges 的 `view` 与 `borrowed_range`，能与标准算法无缝组合；`as_bytes` 系列便于进行低层字节访问。 |\n",
    "| C++23             | 规范化所有特化为 `TriviallyCopyable`；新增 `const_iterator` / `const_reverse_iterator` 的标准定义；`cbegin`/`cend`/`crbegin`/`crend` 成员正式纳入。 | 明确 ABI 特性，跨平台行为一致；迭代器 API 更完整，匹配其他容器接口习惯；在泛型代码中可直接使用 `const_iterator` 等别名，提升可读性。 |\n",
    "| C++26（提案阶段） | 提案增加带界检查的 `at()` 成员（特性宏 `__cpp_lib_span`=202311L）；允许从 `std::initializer_list` 构造 span（特性宏 `__cpp_lib_span_initializer_list`=202311L）；所有成员标注 `constexpr`（受底层数据限制）。 | `at()` 为运行期提供安全访问手段，避免越界；从 `initializer_list` 构造使函数参数更灵活（需注意临时对象生命周期）；若实现支持，可在 constexpr 环境中更广泛使用 span（仍需保证底层存储在常量求值内有效）。 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `std::mdspan<T, Extents, Layout, Accessor>`（C++23）\n",
    "\n",
    "- https://en.cppreference.com/w/cpp/container/mdspan.html\n",
    "\n",
    "| 字段       | 内容                                                         |\n",
    "| ---------- | ------------------------------------------------------------ |\n",
    "| 实现细节   | 多维视图：数据指针 + 维度 + 布局策略；不拥有内存；支持 `constexpr` |\n",
    "| 优点       | 灵活表达多维数据；支持自定义布局（行主/列主）与访问器；零拷贝 |\n",
    "| 缺陷       | 生态仍在完善；接口复杂；需编译器/库支持                      |\n",
    "| 时间复杂度 | 单点访问：O(1)；遍历取决于访问模式                           |\n",
    "| 空间复杂度 | O(r) 存储维度与步长（r 为维度数）                            |\n",
    "| 常见互转   | 可从 `span`、`vector`、`array`、原生指针 + 尺寸构造；可转换为 `span`（通过 `submdspan`/`mdspan.data()` + 线性布局）；配合 `ranges::to` 可生成持有容器（`vector` 等） |\n",
    "\n",
    "\n",
    "- 版本关键变化\n",
    "\n",
    "| 版本              | 关键变化                                                     | 影响 / 备注                                                  |\n",
    "| ----------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| C++23             | 首次标准化 `std::mdspan` 及相关基础设施：`std::extents`/`std::dextents`、默认布局策略（`layout_left`/`layout_right`/`layout_stride`）、`default_accessor` 等；`mdspan` 保证可拷贝、`noexcept` 移动/赋值/交换。 | 统一的多维视图抽象，可针对任意内存布局（含稀疏、对齐访问等自定义策略）配置映射与访问；解耦数据、布局、访问策略，显著提升数值计算/图形渲染等领域的泛型表达能力；保持 `TriviallyCopyable`（取决于策略类型），便于按值传递与 ABI 兼容。 |\n",
    "| C++26（提案阶段） | 扩展子视图与布局生态：`std::submdspan`、`submdspan_extents`、`full_extent_t`、`strided_slice` 等支持按片段/步长生成子视图；新增 `dims` 便捷别名、`layout_left_padded`/`layout_right_padded` 带填充布局；`aligned_accessor` 用于对齐访问。 | 使 `mdspan` 更贴近 Fortran/MATLAB 式切片操作，便于实现张量分块、子矩阵等高性能算法；填充布局与对齐访问可减少缓存伪共享、满足 SIMD/硬件加速需求；配合未来 feature-test 宏（`__cpp_lib_submdspan`、`__cpp_lib_aligned_accessor` 等）便于按需启用新能力。 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# C++11 之后各类容器删除元素的方式与注意事项\n",
    "\n",
    "- C++11 起 `erase` 返回后继迭代器，大幅简化遍历删除代码。\n",
    "- 使用 `erase-remove` 习惯模式处理顺序容器按值删除。\n",
    "- C++20 `std::erase`/`erase_if` 为常见删除模式提供统一接口，但底层规则与 C++11 一致。\n",
    "- 熟悉每类容器的迭代器失效、复杂度和额外限制，是写出稳定高性能删除逻辑的关键。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| 容器类别 / 典型容器                                          | 主要删除接口（C++11 及以后）                                 | 复杂度 / 行为概述                                            | 注意事项与补充                                               |\n",
    "| ------------------------------------------------------------ | ------------------------------------------------------------ | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| **顺序容器**<br>- `std::vector`<br>- `std::deque`<br>- `std::string` | - `erase(iterator pos)`<br>- `erase(iterator first, iterator last)`<br>- `erase(iterator)` 返回 **后继迭代器**（自 C++11）<br>- `remove` / `remove_if` + `erase` 组合<br>- C++20 起：`std::erase(container, value)`、`std::erase_if(container, pred)` | - `erase`：线性时间移动元素（vector/string）、常数或线性（deque）<br>- `remove` 族仅移动元素，需配合 `erase` 真正删除 | - `erase` 会导致后续元素前移，**迭代器/引用/指针失效**（`vector`、`string` 全部；`deque` 受影响区段）<br>- `remove` 仅重排，别忘记 `erase` 剩余尾部元素；<br>- 对大容器频繁删除可改用 **swap+pop_back** 等技巧减小移动成本 |\n",
    "| **链式顺序容器**<br>- `std::list`<br>- `std::forward_list`   | - `erase(iterator)`、`erase(first, last)`（`forward_list` 为 `erase_after`）<br>- `remove(value)`、`remove_if(pred)` 成为成员函数（保留 C++03 行为）<br>- C++20：`std::erase`/`erase_if` 可用 | - `erase` 常数时间（已知节点）<br>- `remove` 族线性遍历      | - `list`/`forward_list` 删除节点 **不使其他迭代器失效**（删除元素的迭代器失效）<br>- `forward_list` 无法单向定位前一个节点，删除前需保存前驱（或用 `erase_after`） |\n",
    "| **有序关联容器**<br>- `std::set`/`multiset`<br>- `std::map`/`multimap` | - `erase(iterator pos)` 返回后继迭代器（自 C++11）<br>- `erase(const key_type&)`：返回删除数量（`set/map` 0 或 1）<br>- `erase(iterator first, iterator last)`<br>- C++20：`erase_if(container, pred)` | - `erase(key)` 对平衡树为 `O(log N)`<br>- 按范围 `erase` 线性于范围长度 | - `erase(iterator)` 仅使被删元素迭代器/引用失效，其余保持有效<br>- `multiset/multimap` 删除特定键需搭配 `equal_range` 或范围 `erase` |\n",
    "| **无序关联容器**<br>- `std::unordered_set`/`unordered_multiset`<br>- `std::unordered_map`/`unordered_multimap` | - `erase(iterator pos)`、`erase(const key_type&)`（返回删除数量）<br>- `erase(iterator first, iterator last)`<br>- C++20：`erase_if(container, pred)` | - 平均 `O(1)`，最坏 `O(N)`（哈希冲突严重）                   | - `erase` 仅使被删元素迭代器失效；桶重哈希时其他迭代器也失效<br>- 删除后保持负载因子，必要时调用 `reserve` 控制 |\n",
    "| **容器适配器**<br>- `std::stack`<br>- `std::queue`<br>- `std::priority_queue` | - **无随机位置删除接口**<br>- 只能通过 `pop()` 移除栈顶/队头元素 | - `pop()` 常数时间                                           | - 若需按值删除，需改用底层容器或其他结构，如 `std::deque` 手动管理 |\n",
    "| **`std::array`**                                             | - 固定大小，**无元素删除**                                   | -                                                            | - 若需标记逻辑删除，可配合哨兵值或有效长度计数               |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**迭代器失效规则**\n",
    "\n",
    "- 顺序容器（特别是 `vector`、`string`）使用 `erase` 后，删除点及其之后的迭代器/引用全部失效；删除前保存需要的迭代器。\n",
    "- 链式容器仅失效被删除节点的迭代器，其余保持有效。\n",
    "- 无序容器在重哈希时所有迭代器失效（即使没直接删除）。删除元素前后若进行了插入可能触发 rehash，需调用 `reserve` 或 `rehash` 控制。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**返回值变化（C++11 新特性）**\n",
    "\n",
    "- `erase(iterator)` 返回指向被删除元素之后的迭代器，方便循环中写法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "for (auto it = container.begin(); it != container.end(); /* no increment here */) {\n",
    "    if (should_erase(*it)) {\n",
    "        it = container.erase(it); // C++11 起可直接接收后继迭代器\n",
    "    } else {\n",
    "        ++it;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**`erase` vs `remove`**\n",
    "\n",
    "- `remove` / `remove_if` 是算法（`<algorithm>`），不会改变容器大小，只将未删除元素前移并返回新逻辑终点。\n",
    "- 支持成员 `remove` 的容器（`list`/`forward_list`）是真正删除节点，无需额外 `erase`。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**C++20 `std::erase` / `std::erase_if`**\n",
    "\n",
    "- 统一为可修改容器（`string`、`vector`、`map`、`unordered_map` 等）提供按值或谓词删除的便利 API，由标准库内部调用 `erase` 完成实际工作。\n",
    "- 对多数顺序与关联容器都可直接使用（容器适配器、`array` 不支持）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**并发与异常安全**\n",
    "\n",
    "- 删除操作通常满足强异常安全（成功删除或不变），但自定义比较器/哈希可能抛异常时需谨慎。\n",
    "- 在并发环境，除非容器有线程安全保证（如 `concurrent_vector`），否则需外部同步。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**多键容器 (`multi\\*`)**\n",
    "\n",
    "- 删除所有相同键：`container.erase(key)` 会移除所有匹配元素。\n",
    "- 精确控制数量：结合 `equal_range` 获取范围，再用 `erase(first, last)`。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**性能考量**\n",
    "\n",
    "- 顺序容器频繁中间删除成本高，尽量后移删除或改用链式容器。\n",
    "- 对于 `vector`，若不在意顺序，可采用 `swap` 到末尾再 `pop_back()` 的技巧："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "void fast_remove_unordered(std::vector<T>& v, size_t idx) {\n",
    "    std::swap(v[idx], v.back());\n",
    "    v.pop_back();\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**自定义类型**\n",
    "\n",
    "- 需保证析构、移动、赋值等操作代价可控，特别是在 `erase` 会触发大量元素移动时。\n",
    "- 对 `pmr` 容器，删除后内存通常不会归还给上游资源（如 `monotonic_buffer_resource`），需结合资源策略考虑重用或整体释放。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# C++ 容器的常见工程应用\n",
    "\n",
    "通用工程提示\n",
    "\n",
    "- 线程安全：标准容器不是并发安全的。多线程读可并发，任一写操作需外部同步；unordered 容器 rehash 时尤其注意。\n",
    "- 构造/搬移：优先使用 `emplace/emplace_hint` 降低拷贝；对大型对象优先移动语义。\n",
    "- 内存与分配器：所有容器支持自定义分配器；C++17 起可用 PMR（`<memory_resource>`）进行区域化管理。\n",
    "- 异构查找：有序容器用透明比较器 `std::less<>`，无序容器用透明 `Hash/KeyEqual`，可避免临时对象与二次构造。\n",
    "- 节点操作：关联/无序关联容器支持 `node_handle`（`extract/insert/merge`）在 O(1) 范围内迁移节点。\n",
    "- 批量构建：读多写少的数据结构（`flat_map/flat_set/vector` 排序+二分）在构建后查询更快且更省内存。\n",
    "- 算法协作：优先使用算法（`std::sort`, `std::lower_bound`, `std::merge` 等）和 `ranges`；`vector` 与 `flat_*` 受益于缓存局部性。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 顺序容器（Sequence Containers）\n",
    "\n",
    "| 容器                       | 典型工程场景                                                 | 关键操作与复杂度                                             | 迭代器/引用失效                                              | 内存/实现要点                                   | 备注/最佳实践                                                |\n",
    "| -------------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ | ------------------------------------------------------------ | ----------------------------------------------- | ------------------------------------------------------------ |\n",
    "| `std::vector<T>`           | - 序列化/反序列化缓冲；网络包/帧缓冲<br>- 科学计算/图形学的连续数值数据（顶点、索引、音频样本）<br>- 数据库/搜索引擎批量结果收集；分页缓存<br>- 游戏/引擎的 ECS 组件存储（稠密 SoA/AoS）<br>- GPU/加速器传输（CUDA/HIP/Metal 的线性内存）<br>- 日志聚合、监控指标批处理<br>- 排序+二分或哈希加速的读多写少表 | 随机访问 O(1)；push_back 摊还 O(1)；末尾增删 O(1)；中间插删 O(n)；reserve 可能 O(n) | 扩容重分配时所有迭代器/引用失效；无重分配时，插入点后的失效；erase 使被删及其后失效 | 连续内存；增长因子实现相关；`bool` 特化为位代理 | 提前 `reserve`；优先 `emplace_back`；erase-remove 惯用法；配合 ranges/算法；PMR 优化分配 |\n",
    "| `std::deque<T>`            | - 实时数据的滑动窗口（信号处理、风控指标）<br>- 日志/审计缓冲；环形近似队列<br>- 生产者-消费者缓冲；任务摄取队<br>- 回退/撤销（undo/redo）历史<br>- 大体量队列（避免 vector 大规模搬移） | 随机访问 O(1)；首尾 push/pop O(1)；中间插删 O(n)             | 首尾操作常使迭代器失效；引用多保持（除被删元素）；实现相关   | 分段连续（块+映射），非单块连续                 | 适作 `queue`/`stack` 底层；不依赖内存连续；注意迭代器失效规则 |\n",
    "| `std::list<T>`             | - LRU/LFU 缓存的链表部分（配合 `unordered_map`）<br>- 作业队列/就绪队列的常数时间 `splice`<br>- 需要稳定迭代器/引用的容器（注册表）<br>- 大对象频繁中间插删（避免搬移）<br>- 多容器之间节点迁移（`merge`/`splice`） | 给定迭代器插删 O(1)；无随机访问；`splice`/`merge` O(1) 链接  | 非擦除修改不失效；擦除仅失效被删元素                         | 双向链表；节点开销大、缓存局部性差              | 仅当确需稳定性/拼接时选择；否则优先 `vector`/`flat_*`        |\n",
    "| `std::forward_list<T>`     | - 单向流水线/流处理（解析器、过滤）<br>- 自由链表/对象池的空闲表<br>- 低内存嵌入式容器；配置加载一次性扫描<br>- 单向图/邻接表的轻量边集 | `insert_after`/`erase_after` O(1)；仅前插/前删               | 迭代器稳定（除被删元素）                                     | 单向链表，节点更轻                              | API 简洁但受限；适用于一次性遍历                             |\n",
    "| `std::array<T, N>`         | - 固定大小缓冲（协议头、矩阵/小向量）<br>- 栈上工作区/临时工作集<br>- 查找表/小型常量表（如 ASCII 映射）<br>- 固定尺寸环形缓冲（自管理读写指针） | 所有操作 O(1)；无 push/pop                                   | 不失效（对象存续期内）                                       | 零开销封装 C 数组；大小编译期                   | 结合 `std::span` 暴露只读/可写视图                           |\n",
    "| `std::basic_string<CharT>` | - 文本/路径/URI/SQL 构造与处理<br>- 配置/日志格式化；报文组装<br>- 命令行/脚本参数拼接；模板替换<br>- 轻量缓存键/字典键 | 随机访问 O(1)；`append`/`insert` 类似 `vector`；`find` O(n)  | 容量变化致全部失效；内容修改常致失效                         | 多数实现 SSO；与 `string_view` 搭配需警惕寿命   | 明确编码（UTF-8/UTF-16）；频繁拼接预留 `reserve`             |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 关联容器（Associative Containers）\n",
    "\n",
    "| 容器                            | 典型工程场景                                                 | 关键操作与复杂度                                             | 迭代器/引用失效                | 内存/实现要点                           | 备注/最佳实践                                                |\n",
    "| ------------------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ | ------------------------------ | --------------------------------------- | ------------------------------------------------------------ |\n",
    "| `std::map<Key, T>`              | - 有序配置/字典；范围/前缀查询<br>- 时间序列按时间戳检索（`lower_bound`）<br>- 调度表/时间轮中的有序槽<br>- 符号表/编译器作用域链（按序遍历生成）<br>- 合并/差集/区间裁剪 | 查/插/删 O(log n)；`lower_bound`/`upper_bound`/`equal_range` O(log n) | 插入不失效；擦除仅失效被删元素 | 平衡树（多为红黑树）；节点分配多        | 透明比较器异构查找（`std::less<>`）；`node_handle` 迁移；读多写少可考虑 `flat_map` |\n",
    "| `std::multimap<Key, T>`         | - 倒排索引（term -> postings）<br>- 事件/信号的多监听者注册表<br>- 多值参数/HTTP 头部同名键<br>- 数据聚类下的键到多实例映射 | 同 `map`；`equal_range` 拿全区间                             | 同 `map`                       | 同 `map`                                | 读密集可改 `map<Key, vector<T>>`（批量更优）                 |\n",
    "| `std::set<Key>`                 | - 去重有序集合；有序导出<br>- 白/黑名单；差并交集合运算<br>- 已访问节点集（需最小/最大弹出）<br>- 有序唯一键索引（如字典序） | 同 `map`                                                     | 同 `map`                       | 同 `map`                                | 合并/差集高效；异构查找减少临时构造                          |\n",
    "| `std::multiset<Key>`            | - 需要计数的有序集合（袋）<br>- 滑动窗口中位数/分位数（双 `multiset` 技巧）<br>- 排队/排行榜允许重复分数 | 同 `map`                                                     | 同 `map`                       | 同 `map`                                | 计数可用 `map<Key, size_t>` 更直接                           |\n",
    "| `std::flat_map<Key, T>` (C++23) | - 小/中规模读多写少：配置/常量表<br>- 嵌入式/缓存敏感场景（连续存储）<br>- 启动期构建一次，运行期频查 | 查 O(log n)（二分）；插/删 O(n)                              | 插/删常致迭代器/引用失效       | 排序的连续存储（常基于 `vector<pair>`） | 批量插入后 `sort`+`unique`；缓存友好                         |\n",
    "| `std::flat_set<Key>` (C++23)    | - 小/中规模有序集合读多写少<br>- 字面量关键字/命令集合匹配   | 同上                                                         | 同上                           | 同上                                    | 构建后查询极快，写入昂贵                                     |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "无序容器（Unordered Containers）\n",
    "\n",
    "| 容器                         | 典型工程场景                                                 | 关键操作与复杂度             | 迭代器/引用失效                                             | 内存/实现要点                                                | 备注/最佳实践                                                |\n",
    "| ---------------------------- | ------------------------------------------------------------ | ---------------------------- | ----------------------------------------------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| `std::unordered_map<Key, T>` | - 缓存/会话/对象注册表（平均 O(1)）<br>- 频次统计/直方图（word count）<br>- 反向索引：ID->位置/偏移<br>- 去重与映射（interning/字符串驻留）<br>- 图/网络邻接表（哈希顶点）<br>- 连接/关联（hash-join 中间表） | 平均查/插/删 O(1)，最坏 O(n) | `rehash` 使全部迭代器失效；擦除仅失效被删元素；引用通常保持 | 装载因子 `load_factor`/`max_load_factor`；自定义 `Hash`/`KeyEqual` | `reserve`/`rehash` 预调桶；透明 `hash`/`equal` 异构查找；`extract`/`merge` |\n",
    "| `std::unordered_set<Key>`    | - 高速成员测试、去重过滤（URL/ID/特征）<br>- 爬虫/流处理的去重集合<br>- 访问/授权快速判定；Bloom 过滤器回退集合<br>- 枚举生成去重后的唯一集合 | 同上                         | 同上                                                        | 同上                                                         | 若需计数用 `unordered_map<Key, size_t>`                      |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 容器适配器（Container Adaptors）\n",
    "\n",
    "| 容器                                         | 典型工程场景                                                 | 关键操作与复杂度                  | 迭代器/引用失效                                      | 内存/实现要点                | 备注/最佳实践                                           |\n",
    "| -------------------------------------------- | ------------------------------------------------------------ | --------------------------------- | ---------------------------------------------------- | ---------------------------- | ------------------------------------------------------- |\n",
    "| `std::stack<T, Container>`                   | - 表达式求值/RPN 计算<br>- 语法解析/括号匹配/回溯（DFS）<br>- 解释器/虚拟机调用帧模拟<br>- 资源/作用域管理（手动栈） | `push`/`pop`/`top` O(1)           | 依赖底层容器（默认 `deque`）                         | 适配 `vector`/`deque`/`list` | 仅暴露栈接口；需遍历时改用底层容器                      |\n",
    "| `std::queue<T, Container>`                   | - BFS/层序遍历<br>- 任务/消息队列（单线程版）<br>- 多阶段流水线缓冲区<br>- IO 提交/完成队（用户态模拟） | `push`/`pop`/`front`/`back` O(1)  | 同上（默认 `deque`）                                 | 同上                         | 并发用专门并发队列或加锁                                |\n",
    "| `std::priority_queue<T, Container, Compare>` | - 调度器/事件驱动仿真<br>- Top-K/流式前 K（新闻热榜）<br>- 最短路径（Dijkstra）、合并 K 路有序流<br>- A*/启发式搜索的开启表 | `push`/`pop` O(log n)，`top` O(1) | 结构变动改变位置；`top` 引用在 `push/pop` 后可能失效 | 默认基于 `vector` 的二叉堆   | 无 decrease-key；可标记删除或重入队；`Compare` 决定堆序 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "视图与轻量容器（Views & Non-owning）\n",
    "\n",
    "| 容器/视图                                           | 典型工程场景                                                 | 关键操作与复杂度                | 生命周期/失效                | 内存/实现要点                            | 备注/最佳实践                                |\n",
    "| --------------------------------------------------- | ------------------------------------------------------------ | ------------------------------- | ---------------------------- | ---------------------------------------- | -------------------------------------------- |\n",
    "| `std::string_view` (C++17)                          | - 解析协议/日志/配置的零拷贝切片<br>- 子串视图（HTTP 头、CSV 字段、JSON token）<br>- API 只读参数，避免分配<br>- 正则/搜索前的预切片 | 访问 O(1)；`substr`/`find` O(n) | 非拥有；源被销毁/变更即悬垂  | 非 `'\\0'` 结尾；`size` 独立于内容        | 避免绑定临时 `std::string`；与格式化配合高效 |\n",
    "| `std::span<T, Extent>` (C++20)                      | - 统一 C 数组/`vector`/`array` 参数 <br>- IO/文件/内存映射缓冲视图<br>- SIMD/向量化内核的切片传参<br>- 传感器/采样数据窗口 | 访问 O(1)；`subspan` O(1)       | 非拥有；来源寿命需覆盖使用期 | 支持动态/静态 Extent；边界信息显式       | API 设计用 `span` 代替 `ptr+len`             |\n",
    "| `std::mdspan<T, Extents, Layout, Accessor>` (C++23) | - 数值/HPC：矩阵/张量/卷积<br>- 图像处理（行/列/步幅、平面/通道）<br>- GPU/异构内存（行对齐/跨距布局）<br>- 科学计算库的后端无关数据访问 | 下标访问 O(rank)（布局映射）    | 非拥有；底层内存由外部管理   | `layout_right/left/stride`，自定义访问器 | 解耦布局与存储；利于缓存与并行划分           |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 标准库容器与其“典型底层数据结构”\n",
    "\n",
    "- 顺序容器（Sequence Containers）\n",
    "\n",
    "| 容器                       | 标准  | 典型底层数据结构                      | 连续内存   | 迭代器失效要点                                               |\n",
    "| -------------------------- | ----- | ------------------------------------- | ---------- | ------------------------------------------------------------ |\n",
    "| `std::vector<T>`           | C++98 | 动态扩容的“连续数组”                  | 是         | 扩容或插入/删除导致“后面元素”的迭代器/引用失效；`push_back` 摊还 `O(1)` |\n",
    "| `std::deque<T>`            | C++98 | 分段（块状）数组 + 中央索引表         | 否（整体） | 在端部插入/删除通常不使其他迭代器失效；中间插入可能失效      |\n",
    "| `std::list<T>`             | C++98 | 双向链表（节点式）                    | 否         | 插入/删除不使其他迭代器失效（被删元素除外）                  |\n",
    "| `std::forward_list<T>`     | C++11 | 单向链表（节点式）                    | 否         | 同上，单向遍历                                               |\n",
    "| `std::array<T, N>`         | C++11 | 固定大小的“连续数组”                  | 是         | 尺寸编译期固定，不涉及扩容                                   |\n",
    "| `std::basic_string<CharT>` | C++98 | 连续字符数组（常带 SSO 小字符串优化） | 是         | 扩容、修改可能使迭代器/指针失效；视实现有 `SSO`              |\n",
    "\n",
    "关联容器（Associative Containers，按键有序）\n",
    "\n",
    "| 容器                    | 标准  | 典型底层数据结构                             | 复杂度                                | 迭代器失效要点                              |\n",
    "| ----------------------- | ----- | -------------------------------------------- | ------------------------------------- | ------------------------------------------- |\n",
    "| `std::map<Key, T>`      | C++98 | 平衡二叉搜索树（常见为红黑树）               | 查找/增删 `O(log n)`                  | 插入/删除不使其他迭代器失效（被删元素除外） |\n",
    "| `std::multimap<Key, T>` | C++98 | 同上                                         | 同上                                  | 同上                                        |\n",
    "| `std::set<Key>`         | C++98 | 平衡二叉搜索树（常见为红黑树）               | 同上                                  | 同上                                        |\n",
    "| `std::multiset<Key>`    | C++98 | 同上                                         | 同上                                  | 同上                                        |\n",
    "| `std::flat_map<Key, T>` | C++23 | 排序的“连续数组”（类似 `vector<pair<...>>`） | 查找 `O(log n)`，插入/删除通常 `O(n)` | 非 C++17 标准内容                           |\n",
    "| `std::flat_set<Key>`    | C++23 | 排序的“连续数组”                             | 同上                                  | 非 C++17 标准内容                           |\n",
    "\n",
    "无序容器（Unordered Containers，哈希）\n",
    "\n",
    "| 容器                              | 标准  | 典型底层数据结构                         | 复杂度                | 迭代器失效要点                                            |\n",
    "| --------------------------------- | ----- | ---------------------------------------- | --------------------- | --------------------------------------------------------- |\n",
    "| `std::unordered_map<Key, T>`      | C++11 | 哈希表（桶数组 + 分离链接法的链表/节点） | 均摊 `O(1)` 查找/增删 | `rehash`/扩容会使迭代器失效；`erase` 使被删元素迭代器失效 |\n",
    "| `std::unordered_set<Key>`         | C++11 | 同上                                     | 同上                  | 同上                                                      |\n",
    "| `std::unordered_multimap<Key, T>` | C++11 | 同上                                     | 同上                  | 同上                                                      |\n",
    "| `std::unordered_multiset<Key>`    | C++11 | 同上                                     | 同上                  | 同上                                                      |\n",
    "\n",
    "容器适配器（Container Adaptors）\n",
    "\n",
    "| 适配器                                       | 标准  | 默认底层容器          | 典型数据结构/算法                                            |\n",
    "| -------------------------------------------- | ----- | --------------------- | ------------------------------------------------------------ |\n",
    "| `std::stack<T, Container>`                   | C++98 | 默认 `std::deque<T>`  | 由底层容器提供 `push/pop` 的栈语义                           |\n",
    "| `std::queue<T, Container>`                   | C++98 | 默认 `std::deque<T>`  | 由底层容器提供 `push`（尾）/`pop`（头）的队列语义            |\n",
    "| `std::priority_queue<T, Container, Compare>` | C++98 | 默认 `std::vector<T>` | 基于随机访问容器上的二叉堆（`std::push_heap`/`std::pop_heap`） |\n",
    "\n",
    "视图与非拥有“容器”（Views & Non-owning）\n",
    "\n",
    "| 类型                                        | 标准  | 典型表示              | 备注                        |\n",
    "| ------------------------------------------- | ----- | --------------------- | --------------------------- |\n",
    "| `std::string_view`                          | C++17 | 指针 + 长度的只读视图 | 不拥有数据、零拷贝切片      |\n",
    "| `std::span<T>`                              | C++20 | 指针 + 大小的可变视图 | 非 C++17 标准内容           |\n",
    "| `std::mdspan<T, Extents, Layout, Accessor>` | C++23 | 指针 + 维度 + 布局    | 非 C++17 标准内容，多维视图 |\n",
    "\n",
    "补充说明\n",
    "\n",
    "- 标准仅约束复杂度与语义；“典型底层数据结构”是实现常见选择（如 `std::map`/`std::set` 通常为“红黑树”，但标准未强制）。\n",
    "- “节点式（node-based）”容器（如 `std::list`、有序/无序关联容器）在插入时通常不移动其他元素的地址；“连续存储（contiguous）”容器（如 `std::vector`、`std::basic_string`、`std::array`）适合与 C API 互操作（`&v[0]`/`v.data()`）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "root has 2 children\n"
     ]
    }
   ],
   "source": [
    "// 自定义一个简单的 N 叉树节点\n",
    "\n",
    "#include <vector>\n",
    "#include <memory>\n",
    "#include <string>\n",
    "#include <cstdio>\n",
    "\n",
    "struct Node {\n",
    "  std::string value;\n",
    "  std::vector<std::unique_ptr<Node>> children;\n",
    "};\n",
    "\n",
    "{\n",
    "  auto root = std::make_unique<Node>();\n",
    "  root->value = \"root\";\n",
    "  root->children.emplace_back(std::make_unique<Node>());\n",
    "  root->children.back()->value = \"child1\";\n",
    "  root->children.emplace_back(std::make_unique<Node>());\n",
    "  root->children.back()->value = \"child2\";\n",
    "\n",
    "  std::printf(\"%s has %zu children\\n\",\n",
    "              root->value.c_str(),\n",
    "              root->children.size());\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "“通用的层级树结构”指的是不带“排序或搜索不变式”的一般树：每个节点可以有任意数量的子节点，强调“父子层级关系”和“子树操作”，而不是像 `std::map`/`std::set` 那样按键有序或固定二叉结构。\n",
    "\n",
    "核心特征\n",
    "\n",
    "- 节点元素：每个节点存一个 `T`（任意类型的值或数据）。\n",
    "- 子节点集合：每个节点拥有一个“子节点列表”（通常用 `std::vector`、`std::list` 等表示），分支数不受限（`N` 叉）。\n",
    "- 结构操作：支持插入/删除子节点、移动整棵子树、遍历（`preorder`/`postorder`/`level-order`）等。\n",
    "- 关系信息：可选 `parent` 指针/索引、兄弟顺序、深度/高度等元数据。\n",
    "- 用途举例：文件系统目录树、`AST`（抽象语法树）、`DOM`、组织架构、UI 组件树、场景图等。\n",
    "- 与 `std::map`/`std::set` 区别：后者通常用平衡二叉搜索树（多为红黑树）实现，节点按“键”排序、每节点最多两个孩子，强调 `O(log n)` 查找；而“通用层级树”不要求键序、有任意分支、操作关注层级结构本身。\n",
    "\n",
    "常见实现方式（几种思路）\n",
    "\n",
    "- 指针拥有关系：`Node` 拥有 `children`（`std::vector<std::unique_ptr<Node>>`），`parent` 为非拥有指针 `Node*`（或 `std::weak_ptr<Node>`）——简单直观，子树移动只移动指针。\n",
    "- 索引图/邻接表：所有节点放进 `std::vector<Node>`，用“索引”记录 `parent` 与 `children`，便于序列化和稳定句柄。\n",
    "- 入侵式指针：`first_child`/`next_sibling`/`parent` 三指针（左孩子-右兄弟表示），插入/移动子树为 `O(1)`，但需要手动管理生命周期。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 一个精简的 C++17 示例（任意度 N 叉树）\n",
    "// - 用 `std::unique_ptr` 表示“父拥有子”的所有权关系，`parent` 用原始指针 `Node*` 仅作导航，避免循环引用。\n",
    "// - 子树移动通过转移 `std::unique_ptr` 实现，代价低；遍历提供 `preorder` 示例，亦可按需扩展 `postorder`、`BFS`。\n",
    "// - 标准库没有这类“通用树容器”，需要按你的业务需求自定义节点与操作；或选用第三方库（例如 `boost::property_tree` 适合配置/层级数据，但非通用算法容器）。\n",
    "\n",
    "#include <vector>\n",
    "#include <memory>\n",
    "#include <string>\n",
    "#include <functional>\n",
    "#include <cstdio>\n",
    "\n",
    "struct Node {\n",
    "  std::string value;\n",
    "  Node* parent = nullptr;\n",
    "  std::vector<std::unique_ptr<Node>> children;\n",
    "\n",
    "  Node* addChild(std::string v) {\n",
    "    children.emplace_back(std::make_unique<Node>());\n",
    "    Node* child = children.back().get();\n",
    "    child->value = std::move(v);\n",
    "    child->parent = this;\n",
    "    return child;\n",
    "  }\n",
    "\n",
    "  bool removeChild(std::size_t i) {\n",
    "    if (i >= children.size()) return false;\n",
    "    children.erase(children.begin() + static_cast<long>(i));\n",
    "    return true;\n",
    "  }\n",
    "\n",
    "  // 先序遍历：f(当前节点)\n",
    "  void traversePreorder(const std::function<void(const Node&)>& f) const {\n",
    "    f(*this);\n",
    "    for (const auto& ch : children) ch->traversePreorder(f);\n",
    "  }\n",
    "\n",
    "  // 将当前节点作为子树，移动到 newParent 底下（保持相对结构）\n",
    "  void moveTo(Node* newParent) {\n",
    "    if (!newParent || newParent == this || isAncestorOf(newParent)) return;\n",
    "    if (parent) {\n",
    "      auto& siblings = parent->children;\n",
    "      auto it = std::find_if(siblings.begin(), siblings.end(),\n",
    "                             [&](const std::unique_ptr<Node>& p){ return p.get() == this; });\n",
    "      if (it != siblings.end()) {\n",
    "        std::unique_ptr<Node> self = std::move(*it);\n",
    "        siblings.erase(it);\n",
    "        newParent->children.emplace_back(std::move(self));\n",
    "        newParent->children.back()->parent = newParent;\n",
    "      }\n",
    "    }\n",
    "  }\n",
    "\n",
    "private:\n",
    "  bool isAncestorOf(const Node* n) const {\n",
    "    const Node* cur = n;\n",
    "    while (cur) {\n",
    "      if (cur == this) return true;\n",
    "      cur = cur->parent;\n",
    "    }\n",
    "    return false;\n",
    "  }\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "root\n",
      "A\n",
      "A1\n",
      "A2\n",
      "B\n",
      "B1\n",
      "root\n",
      "A\n",
      "A1\n",
      "B\n",
      "B1\n",
      "A2\n"
     ]
    }
   ],
   "source": [
    "{\n",
    "  auto root = std::make_unique<Node>();\n",
    "  root->value = \"root\";\n",
    "  Node* a = root->addChild(\"A\");\n",
    "  Node* b = root->addChild(\"B\");\n",
    "  a->addChild(\"A1\");\n",
    "  a->addChild(\"A2\");\n",
    "  b->addChild(\"B1\");\n",
    "\n",
    "  root->traversePreorder([](const Node& n){\n",
    "    std::printf(\"%s\\n\", n.value.c_str());\n",
    "  });\n",
    "\n",
    "  // 将 A2 移到 B 下\n",
    "  a->children[1]->moveTo(b);\n",
    "\n",
    "  std::puts(\"---- after move ----\");\n",
    "  root->traversePreorder([](const Node& n){\n",
    "    std::printf(\"%s\\n\", n.value.c_str());\n",
    "  });\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第三方库选项\n",
    "\n",
    "- 图（Graph）与网络优化\n",
    "\n",
    "| 库                              | 主要数据结构/算法                       | 代表类型/接口                                                | 特点/适用场景                           |\n",
    "| ------------------------------- | --------------------------------------- | ------------------------------------------------------------ | --------------------------------------- |\n",
    "| `Boost.Graph (BGL)`             | 通用图、属性映射、遍历与最短路/生成树等 | `boost::adjacency_list`、`boost::adjacency_matrix`、`boost::dijkstra_shortest_paths` | 抽象完备、算法丰富、与 `Boost` 生态协同 |\n",
    "| `LEMON`                         | 图与网络优化                            | `ListGraph`、`SmartGraph`、`bfs`、`dijkstra`、`minCostFlow`  | 性能好、接口简洁、研究/工程两相宜       |\n",
    "| `igraph`（C 核心，含 C++ 封装） | 大规模图分析                            | 社区发现、中心性、随机图等                                   | 偏图分析与统计，功能全面                |\n",
    "| `NetworKit`                     | 并行图算法                              | 社区、中心性、连通性                                         | 面向大图与多线程                        |\n",
    "\n",
    "- 通用层级树 / 树形数据\n",
    "\n",
    "| 库                   | 主要数据结构/算法            | 代表类型/接口                      | 特点/适用场景                                  |\n",
    "| -------------------- | ---------------------------- | ---------------------------------- | ---------------------------------------------- |\n",
    "| `tree.hh`            | 通用 `N` 叉树                | `tree<T>`、`tree_iterator`         | 头文件库，直接表示层级树结构                   |\n",
    "| `Boost.PropertyTree` | 层级键值树                   | `boost::property_tree::ptree`      | 读写配置/JSON/XML 的层级结构（非通用算法容器） |\n",
    "| `immer`              | 持久化（不可变）树/向量/映射 | `immer::map`、`immer::flex_vector` | 函数式/持久化数据结构，结构共享、省拷贝        |\n",
    "\n",
    "- 高性能哈希表（无序关联容器增强）\n",
    "\n",
    "| 库                         | 主要数据结构/算法    | 代表类型/接口                                                | 特点/适用场景                      |\n",
    "| -------------------------- | -------------------- | ------------------------------------------------------------ | ---------------------------------- |\n",
    "| `Abseil`                   | 开放寻址哈希、B-Tree | `absl::flat_hash_map`、`absl::node_hash_map`、`absl::btree_map` | 速度与内存表现优秀，接口接近 `std` |\n",
    "| `tsl` 系列                 | Robin/Hopscotch 哈希 | `tsl::robin_map`、`tsl::hopscotch_map`                       | Header-only，高性能哈希            |\n",
    "| `parallel-hashmap (phmap)` | 并行/高性能哈希      | `phmap::flat_hash_map`、`phmap::parallel_flat_hash_map`      | 线程友好变体、内存占用低           |\n",
    "| `ankerl::unordered_dense`  | 高密度哈希           | `ankerl::unordered_dense::map`                               | 头文件库，极快、占用小             |\n",
    "| `Folly F14`                | 向量化哈希           | `folly::F14FastMap`、`folly::F14NodeMap`                     | 面向工程、性能极佳                 |\n",
    "\n",
    "- 有序容器的替代/补强\n",
    "\n",
    "| 库                | 主要数据结构/算法   | 代表类型/接口                                            | 特点/适用场景                                                |\n",
    "| ----------------- | ------------------- | -------------------------------------------------------- | ------------------------------------------------------------ |\n",
    "| `Boost.Container` | 扁平有序容器        | `boost::container::flat_map`、`flat_set`                 | 排序数组实现，缓存友好；C++23 `std::flat_*` 的先行替代       |\n",
    "| `Abseil` B-Tree   | B-Tree 有序容器     | `absl::btree_map`、`absl::btree_set`                     | 插入/遍历局部性更好，替代 `std::map/set`                     |\n",
    "| `GNU PBDS`        | 顺序统计树等        | `__gnu_pbds::tree` + `tree_order_statistics_node_update` | 提供 `order_of_key`/`find_by_order` 能力（GCC 扩展，非标准） |\n",
    "| `Boost.Intrusive` | 入侵式有序/链式容器 | `boost::intrusive::rbtree`、`list`、`slist`              | 不分配节点，零额外开销，适合性能敏感场景                     |\n",
    "\n",
    "- 区间/空间索引与几何\n",
    "\n",
    "| 库                             | 主要数据结构/算法     | 代表类型/接口                              | 特点/适用场景               |\n",
    "| ------------------------------ | --------------------- | ------------------------------------------ | --------------------------- |\n",
    "| `Boost.Geometry`/`Boost.Index` | R-Tree 空间索引       | `boost::geometry::index::rtree`            | 范围/邻域查询、GIS/碰撞检测 |\n",
    "| `Boost.ICL`                    | 区间集合/映射         | `boost::icl::interval_set`、`interval_map` | 合并/差集/覆盖等区间操作    |\n",
    "| `nanoflann`                    | `k` 维 KD-Tree 最近邻 | `nanoflann::KDTreeSingleIndexAdaptor`      | 点云/ANN，头文件库          |\n",
    "| `FLANN`                        | KD-Tree/分层 kmeans   | `flann::Index`                             | 高维近似最近邻搜索          |\n",
    "\n",
    "- 并发与无锁容器\n",
    "\n",
    "| 库               | 主要数据结构/算法 | 代表类型/接口                                                | 特点/适用场景                 |\n",
    "| ---------------- | ----------------- | ------------------------------------------------------------ | ----------------------------- |\n",
    "| `oneTBB`         | 并发容器/调度     | `tbb::concurrent_hash_map`、`concurrent_vector`、`concurrent_queue` | 线程安全容器与任务并行        |\n",
    "| `Folly`          | 并发哈希/队列     | `folly::ConcurrentHashMap`、`folly::MPMCQueue`               | 大规模工程验证、配套工具多    |\n",
    "| `libcds`         | 无锁/有锁自由结构 | `cds::container::MichaelHashMap`、`cds::container::SkipListSet` | 多架构无锁实现，学术/工程兼顾 |\n",
    "| `Boost.Lockfree` | 无锁队列/栈       | `boost::lockfree::queue`、`stack`                            | 低延迟生产者-消费者等场景     |\n",
    "| `libcuckoo`      | 并发 Cuckoo 哈希  | `cuckoohash_map`                                             | 高吞吐并发哈希表              |\n",
    "\n",
    "- 字符串/字典树与压缩结构\n",
    "\n",
    "| 库            | 主要数据结构/算法 | 代表类型/接口             | 特点/适用场景                |\n",
    "| ------------- | ----------------- | ------------------------- | ---------------------------- |\n",
    "| `marisa-trie` | 压缩静态 Trie     | `marisa::Trie`            | 只读字典、低内存、高速查询   |\n",
    "| `cedar`       | Double-Array Trie | `cedar::da`               | 前缀匹配/自动机构建高效      |\n",
    "| `hat-trie`    | 哈希 + Trie       | `hat_trie`                | 混合结构，适合大规模字符串键 |\n",
    "| `sdsl-lite`   | 精简/自描述结构   | FM-Index、Wavelet Tree 等 | 文本检索/压缩数据结构        |\n",
    "\n",
    "- 算法竞赛/通用模板（含多种 DS）\n",
    "\n",
    "| 库                      | 主要数据结构/算法                    | 代表类型/接口                                         | 特点/适用场景                    |\n",
    "| ----------------------- | ------------------------------------ | ----------------------------------------------------- | -------------------------------- |\n",
    "| `AtCoder Library (ACL)` | 线段树/树状数组/并查集/最大流/SCC 等 | `atcoder::segtree`、`fenwick_tree`、`dsu`、`mf_graph` | 头文件库，接口简洁，适合快速落地 |\n",
    "| `KACTL`                 | 常用 DS/算法模板                     | 线段树、最小割、几何等                                | 轻量、偏竞赛/教学                |\n",
    "\n",
    "备注\n",
    "\n",
    "- 以上均为“非标准库”，需自行拉取、集成或通过包管理器（如 `vcpkg`/`conan`）安装。\n",
    "- 选择时可按你的需求聚焦：例如“通用图算法”优先 `Boost.Graph`/`LEMON`，“极致哈希性能”优先 `absl::flat_hash_map`/`ankerl::unordered_dense`/`phmap`，“并发容器”优先 `oneTBB`/`Folly`/`libcds`，“空间索引”优先 `Boost.Geometry::rtree`，“层级树”可用 `tree.hh` 或自行定义 `Node + children`。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
